Thread: Prove That a graph G which is a tree is not an eulerean Graph

1. Prove That a graph G which is a tree is not an eulerean Graph

If G is a tree it has no cycles

My attempt
Assume G is a tree

If G has an Eulerian Circuit then the Eulerian Circuit Must repeat a vertex other than the initial vertex for G to remain a Tree

therefore there is one vertex which has no bridge.

-> it is not a tree

This is not explained as well as I could do.

Maybe there is a much simpler way of showing this.

2. A Eulerian circuit is a loop, but trees have no loops. QED.

(Although that is just a shorthand for what you wrote. I can't think of an easier way...)

3. Thanks , We have not defined a loop. In our definition a tree has no cycles but it does not say it cannot have a circuit.

Cycle ( A closed walk where no vertex is repeated)
Circuit ( A closed walk in which no edge is repeated)

4. Originally Posted by Niall101
Thanks , We have not defined a loop. In our definition a tree has no cycles but it does not say it cannot have a circuit.

Cycle ( A closed walk where no vertex is repeated)
Circuit ( A closed walk in which no edge is repeated)
no cycles is stronger than no circuits. However, a tree is defined to be a graph with no closed walks...

Earlier, by 'loop' I meant a closed walk.

5. Can I say that if it has an Eulerean Graph Then the Uniqueness of the path that connects pairs of vertices is no longer present therefore it cannot be a tree

are all circuits also cycles?

6. Originally Posted by Niall101
Can I say that if it has an Eulerean Graph Then the Uniqueness of the path that connects pairs of vertices is no longer present therefore it cannot be a tree
Yes, although you should point out that it doesn't exist because there are no such paths. The uniqueness isn't the problem, the finding of a path is.

Originally Posted by Niall101
are all circuits also cycles?
No, cycles are circuits (if not vertices are repeater then no edges are repeated).

7. I have found another solution which doesnt rely on circuits or cycles

The number of edges in a tree is n-1
The sum of the degress of the vertices is then 2(n-1) = 2n-2

To have a eulerian graph The degree of every vertex must be even

So Sum of the degress of vertives >= 2n

But 2n-2 is never >= 2n

therefore it cannot be a tree.