I was looking at the PenLift problem on TopCoder, after reading this editorial I now understand how to do it, however there's one thing I don't understand.
A fairly well known theorem states that to go over all of the edges in a connected graph requires numOfOddVertices/2 total paths.
Which theory is this? Also why is it so? My first thought is to find an Eulerian path by adding edges, to make all the vertices have even degrees except 2, since that would allow an Eulerian path. I'm not sure if this is correct, also if it was, how would I know that would be the best way of doing it, it seems greedy but I don't see any proof. Could someone please link me to the theory or explain how it works? Thanks in advance.
Which theory is this?
Graph theory.
Also why is it so?
We need to assume at least one pair of odd-degree vertices.
Lower bound: prove inductively that a graph with 2k odd-degree vertices requires at least k paths. Base case k = 1: trivial. Step k > 1: removing a path from a graph with 2k odd-degree vertices leaves at least 2k-2 = 2(k-1) odd-degree vertices.
Upper bound: augment the graph with k edges connecting pairwise disjoint pairs of odd-degree vertices. Now all vertices have even degree, so there exists an Euler circuit. Delete the new edges from this circuit; k paths remain.
In a graph the number of odd vertices (n) is always zero or an even number. If n = 0 you can traverse the entire graph starting from any point. If n > 0, to traverse the graph, you should always start from one odd vertex and you will end from another odd vertex. Say the number of paths you draw continuously is K.
- if n = 2 you can still traverse the graph from one go. ie starting from one odd vertex and ending at the other. K = 1
- if n = 4 after traversing once you will be left with a sub graph which has 2 odd vertices. you can traverse that sub graph with one go. K = 2
- if n = 6 you will have to traverse the graph 3 times. K = 3
and so on .....
Please read my blog post for more info. http://jeewanthad.blogspot.com/2012/11/eulerian-trail.html
