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 connected graph has 13 edges, 2 vertex of degree 2, 2 vertex of degree 3, 1 vertex of degree 6, and all others of degree 5. But with an unknown vertices.

I read an online article and it says that for it to be a graph, the total number of edges should be even, and e = 2v? But in this case, 13 edges cannot be formed into a graph? which means that there are 5 vertices?

share|cite|improve this question
The claim you're citing is clearly wrong; for example, take the graph with one vertex and no edges, or one vertex and one edge forming a loop. – Zev Chonoles Feb 24 '13 at 11:23
Perhaps what was intended was that the sum of the degrees of the vertices is twice the number of edges. – Gerry Myerson Feb 24 '13 at 11:24
so how do i calculate the number of vertices in the given question? – whyme Feb 24 '13 at 11:45
Please do not vandalize your question. – Trevor Wilson Feb 27 '13 at 20:57

Let $Q$ be the number of vertices of degree $5$. Then the sum of the degrees of the vertices is $(2)(2)+(2)(3)+(1)(6)+(5)(Q)=16+5Q$. On the other hand, the sum of the degrees equals twice the numbeer of edges, which is twice $13$, which is $26$. Set these equal, solve for $Q$, and you'll have the number of vertices of degree $5$, and then you'll have the number of vertices, total.

share|cite|improve this answer

You obviously missed the point in the original source. What you mean is the sum of valency of all vertices of a connected graph is even. (more precisely, the number of vertices of odd valency is even.) and obviously that Total Valency=2 $\times$ No. of Edges. These are trivial results. You can use them to solve the number of vertices. $$2\times 13=5\times x+2\times 2+2\times 3+1\times 6\implies x=2$$. What other thing you could conclude about even is the x should be even (can you say why).

share|cite|improve this answer
I believe there's an extra $x$ in your displayed equation. – Gerry Myerson Feb 24 '13 at 22:31

Once you have the only possible degree sequence (as in the other answers), we should still check that a connected graph with that degree sequence actually exists (perhaps via the Havel-Hakimi Algorithm).

Here's one example (the vertices are ascribed their degrees):

The graph

nauty says it's the only graph up to isomorphism with that degree sequence.

share|cite|improve this answer

Your Answer


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.