1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Commented Feb 24, 2013 at 11:23
  • $\begingroup$ Perhaps what was intended was that the sum of the degrees of the vertices is twice the number of edges. $\endgroup$ Commented Feb 24, 2013 at 11:24
  • $\begingroup$ so how do i calculate the number of vertices in the given question? $\endgroup$
    – whyme
    Commented Feb 24, 2013 at 11:45
  • $\begingroup$ Please do not vandalize your question. $\endgroup$ Commented Feb 27, 2013 at 20:57

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ I believe there's an extra $x$ in your displayed equation. $\endgroup$ Commented Feb 24, 2013 at 22:31
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .