2
$\begingroup$

A graph $G$ has k vertices of odd degree, prove that there is $\dfrac{k}{2}$ non-closed trails on the graph that cover all the edges of the graph exactly once.

Here is my proof:

The graph has $k$ vertices, represent them by the sequence $a_1$,$a_2,$...,$a_k$

Add the $\dfrac{k}{2}$ edges into the graph to connect the $k$ vertices.

{$a_1,a_2$},{$a_3,a_4$},{$a_5,a_6$},...{$a_{k-1},a_k$}, where each pair of curly bracket represents an edge between the two vertices.

Now all $k$ vertices have even degree, which means there is a Eulerian trail T.

Then erase the $\dfrac{k}{2}$ edges, which makes the Eulerian trail break into $\dfrac{k}{2}$ separate trails that traverse all the edges in the original graph $G$ exactly once.

I'm making the assumption that the original graph $G$ is connected. Is this proof rigorous enough? Am I missing anything that might break my proof?Thanks for any help.

$\endgroup$
3
$\begingroup$

Your proof looks good. It might be worth mentioning why $k$ must be even at the start. You do need the assumption that $G$ is connected (or at least can be made connected by adding in $k/2$ extra edges in that way), because otherwise the result would not be true - you need $k/2$ trails just to deal with all the odd-degree vertices, so if there is another nontrivial component that doesn't have any of the odd-degree vertices in then you can't reach it without adding an extra trail.

$\endgroup$
  • 1
    $\begingroup$ About your suggestion mentioning why $k$ must be even. There is a theorem that sum of degrees of all vertices should be even. Since each vertex has an odd degree, for the total sum to be even, $k$ needs to be even. $\endgroup$ – user59036 Jan 23 '17 at 18:21

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.