Euler Circuits and Vertices of Even Degree: Proof and Counter-Proof

[MathNerd]

If a connected graph has a Euler circuit then this implies that all the vertices of the graph have even degree. Is the converse of this argument true? i.e. If a connected graph only contains vertices of even degree does this imply it contains an Euler Circuit?

Could somebody please show me a proof (or counter-proof) of the above statement or at least direct me to a website that contains such a proof?

Thanks.

 

[mathwonk]

well i believe it is well known that this is true so let's just prove it. maybe induction would work. so start with a graph with one edge, then it has to be a loop at one vertex hence it is true. oir do you allow loops?

if not then we have at least two edges and two vertices and it again appears true. Ok now let's see,... how do we make the inductive step? well heck it seems obvious how to prove it... just start walking around the graph, beginning from anywhere. If we ever arrive twice at the same vertex say A, then there is a loop formed by the paths traversed between our first and second arrivals at A. Since no other path has ever been visited twice, this loop is a chain of paths formed by entering and leaving certain vertices.

now erase all those poaths in that loop. That diminishes each vertex visited by exactly two edges. so we are left again with an even graph, possibly not connected. still by induction on the number of edges, every connected component of it has an euler circuit presumably beginning anywhere. so we seem to be able to cobble these together to get an euler circuit of the whole thing. well pretty ugly so far, but it seems perhaps true.

this is probab;ly proved in essentially any book on elementary math, or just type in "bridges of konigsberg" to google.

 

[mathwonk]

gee, the coverage on the websites i found was so shallow that none proved the converse. but i think my argument essentially proves it. i.e. removing the partial circuit described, leaves a finite number of connected graphs, all even, so just go around your partial circuit and take side trips around any connected component of the complement as you come tot hem.

'note that you may assume by induction that a circuit of an even graph may start and end anywhere. or just observe that this is obvious if there exists a circuit at all.