Newsgroups: sci.math
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1998/02/14
Subject: Re: Graph Theory help req.

jons5...@telcel.net.ve (Jos'e H. Nieto) writes:

>  sebarn...@aol.com (SEBarnett) wrote:

> > (1) Use induction on k to prove that the edges of a connected
> > simple graph with 2k edges can be partitioned into paths of length
> > 2....

While Sr. Nieto's proof is gratifyingly concise, I rather like the one
I came up with, on the basis of its easy construction or possibly on
the basis of its algorithmic efficiency.

If the graph has any edges, it must have a vertex of degree two or
greater.  Let V be such a vertex and let U and W be two of its
neighboring vertices.  Removing the edges UV and VW will separate the
graph into at most three components, which we name by the vertices of
{U,V,W} they contain:
  either {UVW}, {U,VW}, {V,UW}, {W,UV}, or {U,V,W}.
If there is no component with an odd number of edges, then removing
the path UVW leaves us with connected components of at most 2k-2
edges, that can have their edges partitioned into 2-paths by the
inductive hypothesis.

If G - {UV,VW} has a component with an odd number of edges, then there
must be at least two such components (because there are an even number
of edges in all).  Examining the five possible cases, we can be sure
that at least one of the components with an odd number of edges is U,
W, or UW.

If U, then take G1 = component U + edge UV.
If W, then take G1 = component W + edge VW.
If UW, then take G1 = component UW + edge UV.

In each case, take G2 = G - G1.

  ___           .'       ___            .'      ________         .'
 /G1 \        .'        /G1 \         .'       /G1      \      .'
 \__U/      .'          \__W/       .'         \__U__W__/    .'
     \    .' ____            \    .' ____             \    .' ____
      V .'  V___/             V .'  V___/              V .'  V G2 \
      .'   / G2 :             .'   / G2 :              .'   / \___/
    .'    W_____:           .'    U_____:            .'    W
  .'       \___/          .'       \___/           .'

In either case, we have made G1 a connected graph with an even number
of edges between 2 and 2k-2.  G2, being the rest of G, must have an
even number of edges and can be seen to be connected.  So we can
inductively partition the edges of G1 and G2 into 2-paths. QED.
I wonder if this theorem may be a contender for having as many
different proofs as the problem of tiling a rectangle with rectangles
that each have an integer edge (see Stan Wagon's "Fourteen proofs of a
result about tiling a rectangle" [Amer Math Monthly 94(1987) 601-617]
and Alexander Shen's "Math Entertainments" [Math Intell
19.1(1997)12-13 and 19.4(1997)49-50]).

Dan Hoey
Hoey@AIC.NRL.Navy.Mil