Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some problems with figuring out these questions about simple graphs. I'm not sure if I'm doing this right.

1.How many different graphs $G=(V,E)$ exist with $V=\{1,2,...,n\}$.
There are $\binom{n}{2}$ different edges. So there $2^{\binom n2}$ different subsets of edges.
2. How many different regular graphs with degree 2 exist and $V=\{1,2,3,4,5,6\}$
I think $\binom{5}{2}$ options to not get a cycle and $\binom{5}{2}\cdot3\cdot2$ options to get a cycle of length $6$.
3. Prove that every graph with $n\geq 2$ vertices, has two vertices with the same degree.
Assume they are all different. The largest can't have degree $\geq n$. As they are all different they must have degree $0,1,...,n-1$. But then the largest one is connected to all. Contradiction as one vertice must have degree $0$.

share|cite|improve this question
1. Yes. 2. What is a graph with degree 2? 3. Yes. – dtldarek Feb 12 '13 at 17:48
@dtldarek I mean that all the vertices have degree 2. – Kasper Feb 12 '13 at 17:53
Those are called 2-regular graphs. I would calculate it by $\frac{1}{2}\binom{6}{3}+\frac{1}{2}\frac{6!}{6}$, but you are right. Check also OEIS. – dtldarek Feb 12 '13 at 18:40

Your Answer


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

Browse other questions tagged or ask your own question.