Question

ACE Workbook:

Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ?  Can anyone give the answer and how to approach these problems. Thanks in advance.

Comments

Since,  Graph 'G'  has total $ (n+2+4+3)$ vertices and 'G'  is connected with minimum no. of edges. So, G must be a tree. So, it should have $ (n+2+4+3-1)$ edges.
Now,  According to Handshaking Lemma,
Sum of degrees of all the vertices in G = 2*No. of Edges in G

So, $n*1 + 2*2 + 4*3 + 3*4 = 2*(n+2+4+3-1)$

---

Thanks ankit.

Answer 1

in directed graph, d⁺(G)=d⁻(G)= |E(G)|.

2.2+4.3=3.4+n.1 ⇒ n=4

Answer 2

Here we can assume that graph is undirected because there is nothing mentioned about in-degree and out-degree of a vertex.

by using sum of degree rule(Handshaking Lemma) we can say that

sum of degree of all vertices in graph = 2*(number of edges in graph)

and  number of edges in a connected graph is must be atleast  (n-1)

(n*1) + (2*2) + (4*3)  + (3*4) = 2*(n+2+4+3-1)

on solving above equation

n=12