1
$\begingroup$

Got pretty strange question in the HW:

$G$ is a connected, simple graph with $|E(G)|$ even. I need to prove that there exist a partition of edges into pairwise disjoint pairs, where each pair is path of length 2. This must be done, using Tutte's theorem for perfect matching, somehow.

The only way I can see it can be done, is by contracting paths of length 2 into one edge, thus creating a graph, that will be more acceptable for Tutte's theorem. I can't see a clear way to do that, though.

Any clue will be highly appreciated.

  • 1
    @joriki: yep --- didn't know what it was called, and was writing my comment at the same time you were writing yours. :)2012-01-06

1 Answers 1

3

Hint: Consider the edge graph of $G$, which is likewise connected. By how much can you increase the number of its connected components when you delete one of its vertices (i.e. an edge of $G$)?

  • 0
    By at most 1. Very neat solution, thank you.2012-01-06