Better Know A Theorem: Regular Graph-Subgraphs

20Jun09

My work on linear programs led me to read up on colouring arguments and eventually to post some remarks on the arXiv wherein I gave a proof ot the following. (See “graph” and “regular” on Wikipedia. A “spanning subgraph” is what you get when you delete some edges, but keep all the vertices.)

For every pair of integers 0<=m<=k, every 2k-regular graph contains a 2m-regular spanning subgraph, and every (2k-1)-regular graph contains a spanning subgraph all of whose degrees are in {2m-1, 2m}.

This has a natural generalization which I did not know how to prove, but seemed like it might be true:

(*) For every integer 0<m<=k, every k-regular graph contains a spanning subgraph all of whose degrees are in {m-1, m}.

How would one possibly prove such a thing? After thinking about it a few times, I opened up my electronic copy of the bible of combinatorial optimization and found this was proved by László Lovász in 1970, again by Bill Tutte in 1978, and again by Carsten Thomassen in 1981.

Thomassen is well-known for giving elegant proofs of hard theorems by making them even harder and then using induction. What I mean by this is that, to prove some statement T with no obvious inductive proof, you make some other stronger statement U such that U implies T, and such that U does have an easy inductive proof. I saw proofs of his that exibited this strategy when learning graph theory (the 5-list-colorability of planar graphs, explained here and here) and again at a recent conference in Montreal.

In this case the strengthened version of (*) is

(**) For every integer 0<m<=k, every graph all of whose degrees are in {k-1, k} contains a spanning subgraph all of whose degrees are in {m-1, m}.

Note that compared to (*), we have relaxed the restriction on the input graph, since a k-regular graph meets the hypothesis of (**). In fact it suffices to prove the following special case of (**):

(***) For every integer 0<k, every graph all of whose degrees are in {k-1, k} contains a spanning subgraph all of whose degrees are in {k-2, k-1}.

To see that (***) implies (**), note that we can repeatedly apply (***) to an input graph with degrees in {d-1, d} to get one with degrees in {d-2, d-1}, then one in {d-3, d-2}, etc. And (***) has a proof that is reasonably straightforward: first note that we can repeatedly delete any edge joining two vertices of degree k, and then we use Hall’s Theorem which is something most undergraduates in discrete math learn here at Waterloo.

Good times with induction!



No Responses Yet to “Better Know A Theorem: Regular Graph-Subgraphs”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: