|
Post by vsiap on Nov 27, 2014 22:20:23 GMT
For some graph G, pick an arbitrary vertex v of odd degree. Take the subset of the graph that is connected to v via some path i.e. the connected component of G that contains v; call this Gv. Since Gv is itself a graph, it must have total degree even, which means there must be another vertex w of odd degree in Gv. Since Gv is connected, that means there must exist a path between v and another odd degree vertex. You can do this for any/every odd degree vertex in G.
|
|