1
$\begingroup$

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that?

Thanks for your time

$\endgroup$
1
$\begingroup$

This is called an eulerian graph, the famous example is the one of Königsberg bridges.

Basically, you can draw the graph without lifting the pencil if all vertices (except maybe two) have even degree (and they are all connected). The proof of this is not hard: you must enter and leave each vertex the same number of time, except maybe the starting and end point of your path, if you don't loop. The converse is a little more difficult but not too hard, it is a nice exercice.

See this page for all the details: http://en.wikipedia.org/wiki/Eulerian_path

$\endgroup$
  • $\begingroup$ What you mention helps in establishing a necessary condition for Eulerian graphs, but not a sufficient one. So in my opinion the the proof is more involved than you make it appear, especially to a beginner. $\endgroup$ – Roy O. Jul 10 '14 at 21:15
  • $\begingroup$ yes ok I add a line $\endgroup$ – Denis Jul 10 '14 at 21:18
  • $\begingroup$ Thank Denis, is just all I need. :) $\endgroup$ – Luis Armando Jul 10 '14 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.