The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
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.
asked in Graph Theory by (23 points) | 37 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.

1 Answer

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

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

Related questions

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
49,434 questions
53,630 answers
70,898 users