König Theorm

Theorem (König): Every graph $G$ with maximum degree $\Delta (G)=r$ is an induced subgraph of some $r$-regular graph $H$.

Proof Idea (Constructive):

The proof constructs the $r$-regular graph $H$ iteratively.

1. Base Case: If the given graph $G$ is already $r$-regular, then $H=G$, and $G$ is an induced subgraph of itself. We are done.

2. Inductive Step: If $G$ is not $r$-regular, it must contain at least one vertex $v$ with degree $de{g}_G(v)<r$. (Specifically, the minimum degree $\delta (G)<r$).

   • Take two identical copies of the current graph (let’s call it $G_i$, starting with $G_0=G$). Call the copies $G_i$ and $G_i^{\prime }$.
   • For every vertex $v$ in $G_i$ such that $de{g}_{G_i}(v)<r$, add an edge between $v$ in $G_i$ and its corresponding vertex $v^{\prime }$ in $G_i^{\prime }$.
   • Call the resulting graph $G_{i+1}$. Note that the original $G$ is an induced subgraph of $G_{i+1}$.
   • The degrees of the vertices that had degree $<r$ in $G_i$ increase by 1 in $G_{i+1}$. Vertices that already had degree $r$ remain unchanged.
   • If $G_{i+1}$ is $r$-regular, we stop, and $H=G_{i+1}$.
   • If $G_{i+1}$ is still not $r$-regular (meaning its new minimum degree is still $<r$), repeat this step with $G_{i+1}$.

3. Termination: This process must terminate because, in each step, we increase the degrees of the lowest-degree vertices. Eventually, all vertices will reach degree $r$. The video suggests this occurs after $k=r-\delta (G)$ iterations, resulting in a graph $G_k$ which is $r$-regular and contains the original $G$ as an induced subgraph.