Euler path

[Crazy Gamer]

"Prove that if you want to draw a graph without lifting your pen and tracing each edge exactly once (it is not necessary to return to the starting point),then the maximum number of odd vertices will be 2 only"

Please help me, I am new to graphs so please explain it a little verbosely if it is possible. I would be grateful to you.

[Saumik Karfa]

Trail : A trail is an alternating sequence of vertices and edges (starts and end on a vertex) with no repeated edge.

Euler's Trail : A trail containing all edges of a graph is called an Euler's trail. and closed (starts and end at same vertex) euler's trail is called euler's circuit.

Eulerian Graph : A graph containing an Euler's circuit is an Eulerian Graph. If you notice above described graph contains an euler's trail.

Claim : A graph with an euler's trail contains at-most  two odd vertices :

Let $G$ be a graph containing, then it is clearly connected.

Let $P$ be an euler's train from a vertex $u$ to $v$.

Let us now construct a new graph $G_1$ by adding a new edge $e$ between $u$ and $v$.

In $G_1$ the trail $P$ together with $e$ forms an euler's circuit.

Then $G_1$ is eulerian. Then every vertex of an Eulerian graph is even degree : See This

Then $u$ and $v$ are the only vertex of odd degree. (Since, $e$ contributed $1$ to each of $u$ and $v$)

[Author]

Posts