0
$\begingroup$

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'$.)

Improve this question
$\endgroup$
6
  • $\begingroup$ For comparison, see mathoverflow.net/questions/362168/… $\endgroup$
    – H A Helfgott
    Commented Jan 9, 2021 at 4:01
  • $\begingroup$ Do you mean "such that every vertex has **out-**degree 4"? $\endgroup$
    – Matthieu Latapy
    Commented Jan 9, 2021 at 18:44
  • $\begingroup$ No, I meant that the in-degree plus the out-degree is 4 (as I say above). $\endgroup$
    – H A Helfgott
    Commented Jan 9, 2021 at 23:00
  • $\begingroup$ OK, but then I am confused by the "at least" statement within the parenthesis. It seems to me that it should be removed, or is there something I misunderstand? $\endgroup$
    – Matthieu Latapy
    Commented Jan 9, 2021 at 23:37
  • 1
    $\begingroup$ Rewrote the question completely, for clarity. $\endgroup$
    – H A Helfgott
    Commented Jan 10, 2021 at 12:02

0

Reset to default

You must log in to answer this question.