I came across with the following question from a book in Graphs (not in English):

Let $T(V,E)$ be a tree with $n\geq 5$ vertices and exactly $3$ leafs.

A. Prove that $T$ has exactly one vertex with degree $3$.

B. Prove that the complement graph of $T$ (lets call it $T'$), is not euler graph.

I proved the first theorem but I think I found an example which disproves B:

Consider graph T with 6 vertices:

enter image description here

The complement graph of $T$ is:

enter image description here

I checked for a few time (I hope it's correct). There are exactly two vertices $v_2,v_5$ that has an odd degree so it's an euler graph.

Where is my mistake?

Leaving that example, I tried to prove it by saying the following: T has 3 lefts so those vertices in graph T' will have n-1 degree. if n is even then we have 3 vertices that has an odd degree meaning that T' is not euler. But what can I say about the n even-case?


Euler graph is a connectivity finite graph which follows one of those conditions:

  • Has exactly two vertices of odd degree. In that case its not a circle.
  • All of the vertices with even degree. In that case its a circle.
  • $\begingroup$ The term "Euler graph" is sometimes used in the weaker sense for a graph in which every vertex has even degree. Have you checked the definition in your book? $\endgroup$ – Servaes Jan 18 at 16:49
  • $\begingroup$ @Servaes Hey, thanks for the reply. Please see my definition. $\endgroup$ – vesii Jan 18 at 16:56
  • $\begingroup$ I think you are right, and the exercise in this form is incorrect. $\endgroup$ – Leen Droogendijk Jan 18 at 17:12
  • $\begingroup$ Btw, you remark in the edit session is incorrect. A graph in which every vertex has degree $4$ is Eulerian, but not a circle. $\endgroup$ – Leen Droogendijk Jan 18 at 17:18
  • 1
    $\begingroup$ @LeenDroogendijk I suspect this is a translation problem, and that the intended word is 'cycle'. $\endgroup$ – Servaes Jan 18 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.