Adding edges and vertices to graph until it becomes regular

discrete mathematicsgraph theory

I am reading of Lovasz's theorem, which asserts that

every graph of maximal vertex degree $s+t-1$ can be partitioned in two graphs of maximal vertex degree $s$ and $t$ respectively.

The following fact is used in the proof:

we can add edges and vertices to our graph until it becomes regular.

I fail to understand, why this is true.

Best Answer

There are many ways to do this; here is one easy-to-describe approach.

Suppose that $G$ is a graph with maximum degree $s+t-1$ and minimum degree $\delta(G) < s+t-1$. Take two disjoint copies of $G$; for each vertex of degree $\delta(G)$ in either copy, add an edge to its twin in the other copy. The result is a graph which still has maximum degree $s+t-1$, but the minimum degree is now $\delta(G)+1$. We can repeat until the minimum degree reaches $s+t-1$ as well.

If the minimum degree started out small, this might give us exponentially large results. For the proof of a theorem, we don't care; however, for an algorithm we might. One way to make this approach more efficient is to:

  1. Take $2k$ disjoint copies of $G$, for some $k$ such that $2k-1 \ge s+t-1 - \delta(G)$.
  2. For each vertex $v$ of degree $\deg(v) < s+t-1$ in $G$, add a regular graph of degree $(s+t-1)-\deg(v)$ on the $2k$ copies of $v$. (Since $2k$ is even, a $d$-regular graph on $2k$ vertices exists for any $d$ such that $0 \le d \le 2k-1$.)

This construction is commonly used for a slightly harder task: turning a bipartite graph with maximum degree $d$ into a $d$-regular bipartite graph. The less-efficient version of the construction preserves the property of being bipartite out of the box. For the more efficient version, we have to be slightly careful about which regular graphs we use, but it can also be made to work.

Related Question