Let $G$ be a finite graph with $n$ vertices and largest degree $k$. Assume that $kn$ is even. Then is it always possible to add edges to $G$ to make it $k$-regular?
On the one hand, if we don't care about loops or multiple edges, then we can make $G$ into a $k$-regular multigraph just be repeatedly adding an edge between two vertices of minimal degree. But what if we do care?
The proof of König's line coloring theorem I saw in class starts like that, but maybe with bipartite graphs it is a special case where everything works fine…
Best Answer
So you are asking if it is possible to add ONLY edges and no additional vertices? If this is the question: No it is not always possible: Take a $k=4$ and a 4-regular graph $H$. Replace an arbitrary edge $uv \in H$ with a path $uu_1v_1v$ (so the endpoints of this path are $u$ and $v$ and $u_1$ and $v_1$ are two additional vertices not in $H$) and call the resulting graph $H'$. Then except for precisely $u_1$ and $v_1$ every other vertex in $H'$ has degree 4.
There is no way to add edges to $H'$ to bring $u_1$ and $v_1$ to degree 4 without either (a) making some of the other vertices degree 5 or larger, or (b) adding more vertices.