-1
$\begingroup$

Given a set of nodes $V$, and a parameter $c \lt |V|$,

  1. How can we show that whether we can derive an un-directed graph $G=(V,E)$ where the degree of each node equals to $c$?

  2. If a graph as above exists, how many un-directed edges are there in $G$?

  • 0
    You may as well have said c<|V|, since it's not possible to have $c=|V|$.2012-07-05

2 Answers 2

2

For 2., you want to use that the sum of the degrees is twice the number of edges, as Matt points out in the comments to the question. For 1., you should just construct a graph --- try putting the points in a circle, and try connecting each vertex to some of them that are near it on the circle. Hint: you'll have to do cases for if $c$ is even or odd.

0

By the Handshaking Lemma, there are $\frac{cn}{2}$ edges in a $c$-regular graph on $n$ vertices.

Hence, for a $c$-regular graph on $n$ vertices to exist, we require that $cn$ is even. We also have the obvious necessary condition that $c \in \{0,1,\ldots,n-1\}$. It turns out these conditions are sufficient:

  • If $n$ is even, then we can construct $c$-regular graphs, for any $c \in \{0,1,\ldots,n-1\}$, by taking the complete graph $K_n$ and deleting $1$-factors. (This can always work, since $K_n$ contains a $1$-factorisation.)

  • If $n$ is odd, then we can construct $c$-regular graphs, for any $c \in \{0,2,\ldots,n-1\}$, by taking the complete graph $K_n$ and deleting Hamilton cycles. (This can always work, since $K_n$ contains a Hamilton decomposition.)

Hence we have necessary and sufficient conditions:

Theorem: There exists a $c$-regular graph on $n$ vertices if and only if $c \in \{0,1,\ldots,n-1\}$ and $cn$ is even.