2

Now we know that if number of odd degree vertices in a graph is $0$ or $2$ it an Euler path and if its higher it doesn't. I want to know if its indeed higher, in how many Euler paths can you cover the whole graph? You can start and end at any vertex and delete each edge after you cross it. How many times do you start till the graph is devoid of edges?

My friend says its 1 for no. of odd vertices${}=0$ or $2$; and $+1$ path for every pair of odd degree vertices beyond $2$. For example if there are $6$ odd degree vertices the number of Euler paths${}= 3$, since $6$ is $4$ more than $2$. Is this right or can it be lesser than this?

Marc van Leeuwen
  • 115,048
aravind
  • 21
  • Are you asking about Euler paths or Hamiltonian paths? The question says Euler paths, but then there's a mention of "delete each vertex after you cross it" which would indicate Hamiltonian paths. And the question of finding Hamiltonian paths is much, much harder than the question of finding Euler paths. – Daniel Schepler Oct 12 '18 at 20:34
  • I've changed vertex to edge, which seems to be to only thing that makes sense. – Marc van Leeuwen Oct 13 '18 at 10:10

1 Answers1

1

Keeping in mind that there are always an even number of odd vertices due to the Handshaking Lemma, for a connected graph, the number of required paths is half the number of odd vertices. This can be seen by pairing up all but two of the odd vertices, and adding "dummy" edges between each pair to convert them to even vertices. This modified graph has only two odd vertices, so there's an Eulerian path from one of the remaining odd vertices to the other. Removing the n/2-1 dummy edges from this path results in n/2 separate paths, which go through each edge exactly once.

I should (and will) add that Euler's original argument shows it must be at least n/2.

MJW
  • 131