0
$\begingroup$

If $D$ is a minimally strongly connected digraph, prove that there exists a vertex with exactly one arc leaving it and exactly one arc entering it.

My thoughts are to approach this with respect to the ear decomposition, but I'm having trouble arriving at a contradiction.

$\endgroup$
0
$\begingroup$

Since $D$ is strongly connected it has an ear decomposition $D_1, \ldots, D_n \subset D$ where the $D_i$ are directed paths.

If $D_n$ has length greater than 1, then it has an internal vertex $v$. Since $D_1, \ldots, D_n$ was an ear decomposition, this vertex cannot appear in any $D_i$ for $i < n$. Thus $v$ has indegree and outdegree of exactly $1$.

If $D_n = (v_1, v_2) $ has length exactly 1, then $v_1$ and $v_2$ already appear in some $D_i$ and $D_j$ for $i, j < n$. This means that removing the edge $(v_1, v_2)$ from $D$ leaves a strongly connected graph, which contradicts the fact that $D$ was minimally strongly connected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.