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?
$\endgroup$ 02 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ 2
