112 views
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.
| 112 views
+5
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)$
+1
Thanks ankit.

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

2.2+4.3=3.4+n.1 ⇒ n=4
by (31 points)

by (351 points)