# A vertex $v$ is extendible if and only if $G − v$ is a forest.

I need help understanding the solution to this problem. This problem has been answered here, however, my doubt is not addressed.

Problem: Let $$G$$ be a connected Eulerian graph with at least $$3$$ vertices. A vertex $$′v′$$ in $$G$$ is extendible if every trail beginning at $$′v′$$ can be extended to form an Eulerian Circuit.

Prove following statement: A vertex $$v\in V(G)$$ is extendible if and only if $$G-v$$ is a forest.

Solution :

Necessity: We prove the contrapositive. If $$G − v$$ is not a forest, then $$G − v$$ has a cycle $$C$$ . In $$G − E(C)$$ , every vertex has even degree, so the component of $$G − E(C)$$ containing $$v$$ has an Eulerian circuit. This circuit starts and ends at $$v$$ and exhausts all edges of $$G$$ incident to $$v$$, so it cannot be extended to reach $$C$$ and complete an Eulerian circuit of $$G$$.

Sufficiency: If $$G −v$$ is a forest, then every cycle of $$G$$ contains $$v$$ . Given a trail $$T$$ starting at $$v$$, extend it arbitrarily at the end until it can be extended no farther. Because every vertex has even degree, the process can end only at $$v$$. The resulting closed trail $$T'$$ must use every edge incident to $$v$$, else it could extend farther. Since $$T'$$ is closed, every vertex in $$G − E(T' )$$ has even degree. If $$G − E(T)$$ has any edges, then minimum degree at least two in a component of $$G − E(T)$$ yields a cycle in $$G − E(T')$$; this cycle avoids $$v$$, since $$T'$$ exhausted the edges incident to $$v$$. Since we have assumed that $$G − v$$ has no cycles, we conclude that $$G − E(T')$$ has no edges, so $$T'$$ is an Eulerian circuit that extends $$T$$.

Please explain the necessity part, especially the highlighted part.

The definition of extendable says that every trail starting at $$v$$ can be extended to an Eulerian circuit of $$G$$. But the Eulerian circuit we find in $$G - E(C)$$ is a trail starting at $$v$$ which cannot be extended any further, contra the definition.
In more detail: removing the cycle $$C$$ only changes degrees by $$2$$, therefore, by the familiar necessary and sufficient condition for the existence of an Euler circuit, as $$G$$ was Eulerian, and so had all vertices of even degree, $$G - E(C)$$ has all vertices of even degree and so each connected component of $$G - E(C)$$ is Eulerian. This provides an Euler circuit $$R$$ in the component of $$v$$ in $$G - E(C)$$ - that is, a closed trail which passes through every edge. In particular, we may choose this trail to start (and so end) at $$v$$; and in particular it passes through every edge incident to $$v$$ (note that this includes every edge incident to $$v$$ in the original graph $$G$$, as the cycle $$C$$ that we removed lies in $$G - v$$).
Then, in $$G$$, we may start at $$v$$ and follow $$R$$ round back to $$v$$ again. We have used up every edge incident to $$v$$, but we have have not visited any edge of $$C$$. So the trail $$R$$ cannot be extended to an Euler circuit of $$G$$.
• We have followed a trail $R$ which has ended at the vertex $v$. There are no unused edges incident to $v$. We cannot extend the trail, because to extend the trail would require moving from $v$ to an adjacent vertex along an unused edge. There are no unused edges incident to $v$, so we cannot move from $v$ to an adjacent vertex along an unused edge, so we cannot extend the trail Commented Jul 17, 2020 at 13:08
• If we take your use of 'extend' then the theorem is false; instead we can say "every trail $T$ in a connected Eulerian graph $G$ forms part of an Euler circuit in $G$", which is rather trivially true, since 1) we have an Euler circuit, which 2) every edge of $T$ appears in. Then we don't get any interesting distinction between vertices which are extendable and vertices which aren't, i.e. you replace an interesting concept with a trivial one Commented Jul 17, 2020 at 13:17