# Proving that the complement graph is not euler graph.

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:

The complement graph of $$T$$ is:

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?

EDIT:

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.
• 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? – Servaes Jan 18 at 16:49
• @Servaes Hey, thanks for the reply. Please see my definition. – vesii Jan 18 at 16:56
• I think you are right, and the exercise in this form is incorrect. – Leen Droogendijk Jan 18 at 17:12
• Btw, you remark in the edit session is incorrect. A graph in which every vertex has degree $4$ is Eulerian, but not a circle. – Leen Droogendijk Jan 18 at 17:18
• @LeenDroogendijk I suspect this is a translation problem, and that the intended word is 'cycle'. – Servaes Jan 18 at 18:24