I have a doubt in the only if part of the proof i.e. if a graph G is connected and it's all vertices has even degree then the graph is eulerian. In this we prove two claims- In the longest path X=(v0,e1,v1,e2,.....,em,vm)

  1. v0=vm (v0 is initial vertex, vm is the last vertex where m is the number of vertices)

  2. set of all ei's in X is the set of edges in G[E(G)]

Doubt- in claim 2 we assume that let the set of edges ei's in X be not equal to E(G) and then end up in a contradiction but how? We assume an edge not in E(X) and say there is a longest path with that edge?

Question - Proof every graph is eulerian if and only if it has all vertices with even degree.

  • $\begingroup$ Question body says "all vertices has even degree" but title says "has even number of vertices". Which is it??? $\endgroup$ – bof Nov 10 '18 at 2:02

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.