# Work out the number of edges given conditions of a graph

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

-
Well, the answer to 2) is $\frac{c|V|}{2}$; each vertex has $c$ adjacent edges, but each edge is counted twice this way because it is adjacent to two vertices. Not sure about 1) though, hence comment not an answer. The answer to 2) says that $c|V|$ being even is necessary, but maybe it's not sufficient. – Matthew Pressland Jul 5 '12 at 16:15
You may as well have said $c<|V|$, since it's not possible to have $c=|V|$. – Rick Decker Jul 5 '12 at 18:22

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.

-

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.

-