# Existence of d-regular graphs

It is well known that if $0<d<n$ and $d\cdot n$ is even then there exist $d$-regular graphs on $n$ vertices. My question is: What is the easiest way to prove this?

-

I. If $0\lt d\lt n$ and $d$ is even, then $C_n^{d/2}$ is a $d$-regular graph of order $n$.

II. Suppose $n$ is even. say $n=2t$. The complete bipartite graph $K_{t,t}=(V,E)$ has a proper edge-coloring $f:E\to\{1,\dots,t\}$. Let $E_d=\{e\in E:f(e)\le d\}$. If $0\le d\le t$ then $G_d=(V,E_d)$ is a $d$-regular graph of order $n$; if $t\lt d\lt n$ then $\overline G_{n-1-d}$ is $d$-regular of order $n$.

-

let $d$ be even. Suppose you have a d-regular graph on n vertices. Then chose a pair of adjacent vertices with degree d and remove an edge,this will give you 2 vertices with degree $d-1$ and leave the other degrees unchanged. Do this $\frac{d}{2}$ times to get d vertices with degree $d-1$ and the rest unchanged. Now join all the vertices with degree $d-1$ to the new vertex to get a d-regular graph on n+1 vertices.

Let d be odd. Suppose there is a d graph on n vertices. then add two new vertices. Pick a vertex and connect it to both of the new vertices. Now pick two edges coming out of this vertex (connected to edges of degree 2). and delete them. Now do the same procedure for even d's delete the edges and connect to one of the new vertices. Then do it again for the other new vertex and you get a d-regular graph on $m+2$ vertices.

-
This is a good proof, and it's pretty simple, but don't we still have to show something? In the even case, there's an implicit assumption that the original n vertex graph has a matching with d/2 edges, and in the odd case there's a stronger assumption. we need a union of two disjoint matchings - one for each new vertex. Do these assumptions always hold true? – Zur Luria Dec 24 '13 at 19:43
And this is not easy to prove? – Carry on Smiling Dec 24 '13 at 20:14