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$ Commented Jan 9, 2021 at 4:01
  • $\begingroup$ Do you mean "such that every vertex has **out-**degree 4"? $\endgroup$ 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$ 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$ Commented Jan 9, 2021 at 23:37
  • 1
    $\begingroup$ Rewrote the question completely, for clarity. $\endgroup$ Commented Jan 10, 2021 at 12:02

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.