If $d^{+}(v)=1$ for all v in a connected graph $G$, then show G has exactly one circuit.

Question

If $d^{+}(v)=1$ for all v in a (weakly or strongly) connected graph $G$, then show G has exactly one circuit.

Let G has n vertices. Number the vertices $1,2,...,n$ Since G has n edges, and WLOG $1,2,...,n$ is connected with n-1 edges, and $d^{+}(n)=0$ Wherever n points out to would yield one circuit. Is this correct? If I’m right I’d answer my own question.

Answer 1

NOTE

I am assuming that you learned this already: IF not, please let me know.

Claim 1: A connected (undirected) graph $G$ on $n$ vertices and $n$ edges has exactly one cycle.

Claim 2: Let $C$ be a connected directed graph where every vertex has indegree AND outdegree exactly 1. Then $C$ is a circuit.

Claim 3: Let $H$ be a digraph, and let $G$ be the undirected graph such that the edge $uv$ is in $G$ iff either $uv$ or $vu$ is in $H$. Then if $C$ is a circuit in $H$ with at least 3 vertices, then the set of edges $\{uv; uv \in A(C)\}$ [where $A(C)$ is the set of arcs $uv \in H$ such that the edge $uv$f is part of the cycle $C$ in $G$] form a cycle in $G$.

So now let $H$ be a directed graph where $d^+(v) =1$ for each $v \in H$. Then there are exactly as many arcs as vertices in $H$. So let $G$ be the undirected graph, where $uv \in G$ if either $uv$ of $uv$ is in $H$. Then $G$ is also connected, and has no more than $|A(H)| = |V(H)| = |V(G)|$ edges--depending on whether there is a pair of vertices $u,v$ such that both $uv$ and $vu$ are arcs in $H$. We consider 2 cases.

Case 1: There is a pair of vertices $u,v$ sucvh that both $uv$ and $vu$ are in $H$. Then as $G$ is connected it must have at least $|V(G)|-1$ $= |A(H)|-1$ edges, so there is exactly one such pair $u,v$. Furthermore, $G$ is a tree. Thus by Claim 3 the only possible circuit in $H$ is $\{uv, vu \}$.

Case 2: There is no such pair $u,v$. Then $|E(G)|= |V(G)|$ and so by Claim 1 $G$ has exactly one cycle $C$. This implies that $H$ has at most one possible cuircuit, namely the set of arcs $\{uv \in H; uv \in E(C)\}$. We now show that $C$ is indeed a circuit in $H$, finishing the proof.

However, letting $X$ be the set of vertices in $C$ and $A(C)$ be the set of arcs $uv$ in $H$ s.t. $uv$ is an edge in $C$, we note that $|X|=|A(C)|$. We also note that every vertex in $C$ is incident to exactly two arcs in $A(C)$. Therefore, as every vertex $v \in H$ has outdegree exactly 1, it follows that every vertex in $C$ has outdegree exactly 1 in $A(C)$, lest there exists a vertex in $C$ with outdegree 2. So every vertex $v \in C$ has exactly one remaining edge incident to it in $A(C)$, which implies that every vertex has indegree exactly 1 in $A(C)$. Now $C$ is connected as it is a cycle in $G$. Thus Claim 2 implies that $C$ is indeed a circuit, finishing the proof.

---

Just because $H$ as specified above has only 1 circuit does not mean that $H$ is a circuit. Can you specify a connected digraph where every vertex has indegree exactly 1 that is not a circuit?