Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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).
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):
nauty says it's the only graph up to isomorphism with that degree sequence.
