discrete maths graph, vertices edges

Question

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?

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

score 1 · Answer 1 · 2013-02-24T22:51:19.603

1

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

edited Feb 24 '13 at 22:51

answered Feb 24 '13 at 11:50

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

score 1 · Answer 2 · answered Feb 24 '13 at 22:31

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.

score 0 · Answer 3 · answered Aug 05 '13 at 16: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.

discrete maths graph, vertices edges

3 Answers3