# Existence of k-regular graph

In a few examples i noted that the existence of $k$-regular graph on n vertices is :

1. True , for k or n even.
2. False , for k and n odd . But we can find a graph with $n-1$ vertices with degree k and one vertex with degree $k-1$. There doesn't exists a k-regular graph for k and n odd because $k=\deg(G) = 2*|E(G)| / |V(G)|$ $|E(G)| = k*n/2$, and $|E(G)|= m$ is not a natural number if $n$ and $k$ is odd.

Any proof idea ??

-
What is it you're having trouble proving? – Qiaochu Yuan Nov 22 '10 at 23:57

There is a theorem (Erdos-Gallai) on degree sequences:

$\displaystyle d_i$ is a degree sequence of some graph if and only if

$\displaystyle \sum_{i=1}^{m} d_i \leq m(m-1) + \sum_{i=m+1}^{n} \min \{d_i, m\} \ \ \text{for} \ \ m \in \{1,2, \dots, n\}$

and

$\displaystyle \sum_{i=1}^{n} d_i$ is even.

It should be easy to verify for the case when $\displaystyle d_i = k \ \ \forall i \in \{1,2, \dots, n\}$ (cumbersome verification at the end of the answer).

The case $\displaystyle k=n-1$, we trivially know the existence of a regular graph ($\displaystyle K_n$).

Suppose $\displaystyle k \lt n-1$.

Now for $\displaystyle 1 \le m \le k$ we have that

$\displaystyle m(m-1) + (k-m)m + (n-k)k -mk = nk - k^2 - m \ge nk-k^2 - k = k(n-k-1) > 0$

For $\displaystyle m \gt k$ we have

$\displaystyle m(m-1) + (n-m)k - mk = m^2 - m(2k+1) + nk = (m-(2k+1)/2)^2 +nk - ((2k+1)/2)^2$

For $k \lt n-1$ we have that $\displaystyle 4nk \gt 4k^2 + 4k$

i.e. $4nk \ge 4k^2 + 4k + 1 = (2k+1)^2$.

Hence $\displaystyle m(m-1) + (n-m)k - mk \ge 0$

Thus if $\displaystyle kn$ is even, there exists a $k$-regular graph on n vertices.

The other part I leave to you.

-
@ALbin: Yes, you are right. – Aryabhata Nov 24 '10 at 19:23
Great proof !! But i don't get it for $\displaystyle 1 \le m \le k$ . For me, it is : for $\displaystyle 1 \le m \le k$ we have that :  $\displaystyle m(m-1) + (n-m)m \ge mk$ ( for $\displaystyle 1 \le m \le k$ we have $min\{d_i=k,m\}=m$ )  $\displaystyle m-1 + n-m \ge k$  $\displaystyle n-1 \ge k$ (that is true.) $– Albin. Com. Nov 24 '10 at 19:30 At the outset, you should assume that$k < n$. If$n = 2m$is even, construct a graph with vertex set $$\{ X_i : i \in \mathbb{Z}_m \} \cup \{ Y_i : i \in \mathbb{Z}_m \},$$ where$\mathbb{Z}_m$is the integers modulo$m$. Connect$X_i$to$Y_j$if$j-i \in \{1,\ldots,k\}$, where subtraction is done modulo$m$. Each$X_i$is connected to$Y_{i+1},\ldots,Y_{i+k}$, and each$Y_j$is connected to$Y_{j-1},\ldots,Y_{j-k}$. If$k = 2l$is even, construct a graph with vertex set $$\{X_i : i \in \mathbb{Z}_n\}.$$ Connect$X_i$and$X_j$if$i \neq j$and$i-j \in \{-l,\ldots,l\}$. This relation is symmetric (since$j-i = -(i-j)$), and every$X_i$is connected to$X_{i-l},\ldots,X_{i+l}$. As you mentioned, when both$n,k$are odd, we have$2e = nk$where$e$is the number of edges (this formula is obtained by counting all endpoints of all edges), which is a contradiction. - +1: Nice construction! – Aryabhata Nov 23 '10 at 1:17 The real point is that i must find ex(n, H) , where ex(n,H) is the minimum value such that every graph G on n vertices with |E(G)| ≥ ex(n, H) contains H as a subgraph, and H is the star$ H_{1,r} $. The maximum degree of such G Δ <= r-1.So, using the avarage degree if I find a r-1 regular graph on n vertices all done : $$ex(n,H_{1,r}) = \frac{ \lvert V(G) \rvert * (r-1) } {2}$$. – Albin. Com. Nov 23 '10 at 15:30 But i saw that anyway we can construct a graph strictly similar to r-1 regular: If n and k = r-1 is odd , we can construct a graph with |V(G)| - 1 vertices at degree k (r-1) and one to degree k-1 (r-2). So in that case $$\{ ex(n,H_{1,r}) = \lfloor \frac{ \lvert V(G) \rvert * (r-1) } {2} \rfloor$$ – Albin. Com. Nov 23 '10 at 15:30 For n=2m that's not work if k > m: Because every vertex must have degree k > m and the edges are defined between two set {$ X_i:i∈Z_m $} and {$ Y_i:i∈Z_m \$} of both size m. "If i don't miss understood" – Albin. Com. Nov 23 '10 at 19:07

A lot easier way: the sum of the degrees is 2|E|. Therefore the sum of the degrees must be an even number. Since an odd times an odd is always an odd, and the sum of the degrees of an k-regular graph is k*n, n and k cannot both be odd.

-