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.