Graph theory | Graph Theory

Question

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?

• A. $8$
• B. $13$
• C. $18$
• D. $21$

Comments

18 vertices

---

https://youtu.be/UuFc7kXtqjI

Answer 1

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}$.

Answer 2

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 $

Answer 3

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.