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


*

*True , for k or n even.

*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 ??
 A: 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.
A: 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.
A: 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 $\boldsymbol k$-regular graph is $k\cdot n$, $n$ and $k$ cannot both be odd.
