MathOverflow Asked on February 15, 2021
Let $Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every vertex is $geq 2$. It is allowed to draw arrows on both directions on an edge.
Must there be a connected subset $V’subset V$ (that is, $Gamma_{V’}$ is connected, as an undirected graph) having at least $delta n$ elements in its outboundary?
(Feel free to define the outboundary of $V’$ either as the set of all $w$ not in $V’$ such that there exists an arrow from some vertex in $V’$ to $w$, or as the set of all $w$ in $V’$ such that there exists an arrow from $w$ to some vertex not in $V’$.)
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP