0 votes
74 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.
| 74 views
+4
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.

+2 votes

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

### n=12

by (63 points)
+1 vote
in directed graph, d⁺(G)=d⁻(G)= |E(G)|.

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

0 votes
1 answer
1
0 votes
0 answers
3
0 votes
1 answer
4
+1 vote
1 answer
5
+1 vote
1 answer
6
+1 vote
0 answers
7