Recently, I am reading the book [1]. On pages 16-17, the author wrote:
Theorem 12 A non-trivial connected graph has an Euler circuit iff each vertex has even degree.
A connected graph has an Euler trail from a vertex $x$ to a vertex $y \neq x$ iff $x$ and $y$ are the only vertices of odd degree.
Proof. The conditions are clearly necessary. For example, if $G$ has an Euler circuit $x_1 x_2 \cdots x_m$, and $x$ occurs $k$ times in the sequence $x_1, x_2, …, x_m$, then $d(x) = 2 k$.
We prove the sufficiency of the first condition by induction on the number of edges. If there are no edges, there is nothing to prove, so we proceed to the induction step.
Let $G$ be a non-trivial conneted graph in which each vertex has even degree. Since $e(G) \geq 1$, we find that $\delta(G) \geq 2$, so by Corollary 9, $G$ contains a cycle. Let $C$ be a circuit in $G$ with the maximal number of edges. Suppose $C$ is not Eulerian. As $G$ is connected, $C$ contains a vertex $x$ that is in a non-trivial component $H$ of $G – E(C)$. …
Corollary 9 is:
Corollary 9 A tree of order at least 2 contains at least 2 vertices of degree 1.
My question is: Why does $C$ contain a vertex $x$ that is in a non-trivial component $H$ of $G – E(C)$?
The following is my attempt to answer the above question: First, according to page 6 of [1],
A maximal connected subgraph is a component of the graph.
Then I search for the definitions of "connected" and "subgraph". On page 6 of [1], I find:
A graph is connected if for every pair $\{x, y\}$ of distinct vertices there is a path from $x$ to $y$.
On page 2 of [1], I find:
We say that $G' = (V', E')$ is a subgraph of $G = (V, E)$ if $V' \subset V$ and $E' \subset E$.
Then I don't know how to continue. Could anyone please give me some comments or an answer? Thanks in advance.
Reference
[1] B. Bollobas, Modern Graph Theory, Springer, 1998.
Best Answer
Because by assumption (toward a contradiction) the cycle $C$ is not Eulerian, meaning that there are edges of $G$ that are not in $C$. Because $G$ is connected there is such an edge that connects to a vertex of $C$. So there is a vertex $x$ of $C$ that has an edge in $G-E(C)$, so it is in a nontrivial component of $G-E(C)$.