Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer
    
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
1  
And this is not easy to prove? –  Jorge Fernández Dec 24 '13 at 20:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.