graph theory problem

[galactus]

I have a rather silly question about graph theory. I remember years back, before I ever heard of graph theory, there was a puzzle

going around school. It challenged you to draw the following graph without lifting your pencil or retracing a line. I do not think it

can be done. My question is, what is the proof that it can not be done?. I always end up with one line short. Isn't there a theorem by

Euler which states when a graph can not be drawn under this criteria?. Is this an Euler circuit?.

 

[Deleted member 4993]

If a network has more than two odd vertices, it does not have an Euler path.

That figure has 4 vertices of 5 th degree - so it does not have an Euler path.

reference:

http://mathforum.org/isaac/problems/bridges2.html

 

[galactus]

Thanks, SK. I should've remembered the Konigsburg problem. I knew it had something to do with an Euler 'something', but couldn't remember exactly what.