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.


[1] B. Bollobas, Modern Graph Theory, Springer, 1998.


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

  • 1
    $\begingroup$ How do we know that $V(G) = V(C)$? Consider a 3-cycle with an additional edge emanating from one of the vertices to a fourth vertex not already part of the cycle. Then $V(G) = 4$ but wouldn't $V(C) = 3$? $\endgroup$ – benguin Nov 17 '16 at 12:26
  • 1
    $\begingroup$ Because every vertex of $G$ has even degree; if we can go to a vertex along an unused edge, we can also leave from it along an unused edge. $\endgroup$ – Servaes Nov 17 '16 at 12:29
  • 1
    $\begingroup$ Because $C$ is not Eulerian, there is an edge in $G$ that is not in $C$, say $\{x,y\}$. Then $\{x,y\}$ is an edge of $G-E(C)$, so both $x$ and $y$ are in a nontrivial component of $G-E(C)$. $\endgroup$ – Servaes Nov 17 '16 at 13:03
  • 1
    $\begingroup$ We can say that $x$ and $y$ are in $G-E(C)$ because this graph is obtained from $G$ by only removing edges; every vertex of $G$ is still a vertex of $G-E(C)$. I'm not sure what you mean by "...can we delete the term nontrivial component?". $\endgroup$ – Servaes Nov 18 '16 at 13:40
  • 1
    $\begingroup$ Yes of course; if they are in a nontrivial component of the graph, then they are in the graph. But for the proof you will need the fact that they are in a nontrivial component. $\endgroup$ – Servaes Nov 22 '16 at 2:19

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.