Register to reply

Euler Circuits

by MathNerd
Tags: circuits, euler
Share this thread:
MathNerd
#1
Sep13-04, 10:19 PM
P: n/a
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.
Phys.Org News Partner Science news on Phys.org
Mysterious source of ozone-depleting chemical baffles NASA
Water leads to chemical that gunks up biofuels production
How lizards regenerate their tails: Researchers discover genetic 'recipe'
mathwonk
#2
Sep17-04, 09:37 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,470
well i believe it is well known that this is true so lets 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 lets 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
#3
Sep17-04, 09:46 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,470
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.


Register to reply

Related Discussions
Euler's tricentennial General Math 1
Results same w/ Euler, Improved Euler, & Runge-Kutta Differential Equations 14
Electric circuits problem (RL/C circuits) Introductory Physics Homework 3
What would Euler do? General Math 23