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 ??
Best Answer
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.