edited by
25,176 views
1 votes
1 votes

A simple non directed graph contains $21$ edges, $3$ vertices of degree $4$ and the other vertices are of degree $2$.Then the number of vertices in the graph is?

  1. $8$
  2. $13$
  3. $18$
  4. $21$
edited by

3 Answers

Best answer
2 votes
2 votes
The Handshaking theorem states that,

$\displaystyle{\sum_{v \in V}{deg (v_i)} = 2 \times \mid E\mid}$

Which means, $\text{Each edge contributes twice to the sum of the degrees of all vertices.}$

$\text{Sum of degree of vertices = 2 } \times Edges$

Now, the graph has $21$ Edges.

∴ $2 \times Edges = 2 \times 21 = 42$

We don't know the number of vertices.

So, we assumed the total number of vertices will be $n$

∴ Sum of the degree of vertices = $3 \times 4 + (n-3) \times 2$ $\qquad \left[ \text{3 vertices have degree 4 & other vertices that means (n-3)vertices have degree n} \right ]$

∴ $3\times(4) + (n – 3 ) \times 2 = 2\times(21)$

   Or, $n  = 18$.

∴ $\color{Green}{\text{Number of vertices in the graph is }} \color{Blue}{ 18}$.
edited by
5 votes
5 votes
In any Simple Undirected Graph, We have degree sum formula that :

$\sum_{v \in V} deg(v) = 2\left | E \right |$

Where $\left | E \right |$ is the number of edges.

(We can prove this formula by the fact that every edge in any undirected graph contributes the sum of $2$ in the degree sum formula)

Hence, Just apply this formula :

Let $n$ be the number of Total vertices then we have

$3 \times 4 + (n-3) \times 2 = 2 \times 21$

 $n = 18 $
3 votes
3 votes
Note that the sum of the degrees of vertices is equal to twice the number of edges.

So,here the sum of the degrees =21*2 = 42

Now,assume there are k vertices of degree 2 and we have 3 vertices of degree 4

So, the sum of the degrees of the vertices are (3*4) + 2k

Hence, (3*4) + (2*k) = 42

=> k = 15

So,the total number of vertices is 15 + 3 = 18.

Hence,Option C is the correct answer.

Related questions

0 votes
0 votes
1 answer
2
mb14 asked May 28, 2018
394 views
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition- in a path vertices and edges can't repeat so why this is a path. confused please clarify...
0 votes
0 votes
0 answers
4