The Gateway to Computer Science Excellence
0 votes
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.
in Graph Theory by (147 points) | 112 views
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.

2 Answers

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

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

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



by (351 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,748 answers
108,124 users