Date: 04 Nov 2012 18:39
Number of posts: 2
RSS: New posts
First convince yourself that, in any graph, the number of vertices having an odd degree is even. Consider a graph where this number is $k=2\ell$.
We ask you to show that the edges of the graph can be partitioned into $\ell$ (not necessarily simple) paths. Each edge of the graph should participate in exactly one such path.
Note that we proved the case $\ell=1$ (an Euler path) in recitation.