1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I followed your steps, but in the last paragraph you wrote ' 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' WHY? Trail can be extended to include the E(C), by circling along the comon vertex shared by C and trail T. Explain it ? $\endgroup$
    – beta_me me_beta
    Commented Jul 17, 2020 at 3:20
  • $\begingroup$ 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 $\endgroup$
    – Judy N.
    Commented Jul 17, 2020 at 13:08
  • $\begingroup$ It seems you are fundamentally misunderstanding what is meant to "extend" a trail. It does not simply mean "replace it with another, different trail, which happens to share bits of it with the one we started with", that is, 'extending' a trail does not allow adding something 'in the middle' of the trail - that simply turns it in to a different trail to begin with. 'Extending' a trail means following the whole original trail as it already was, then continuing to further vertices along further edges. $\endgroup$
    – Judy N.
    Commented Jul 17, 2020 at 13:13
  • $\begingroup$ 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 $\endgroup$
    – Judy N.
    Commented Jul 17, 2020 at 13:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .