Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Matt 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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.