Graph Theory.

May 2010
12
0
If a graph has 16 vertices, 35 edges and degree set {4, 5}. How many vertices of degree 4 are there?


Please help, it's much appreciated.
 
Last edited by a moderator:
Mar 2010
116
41
Bratislava
If a graph has 16 vertices, 35 edges and degree set {4, 5}. How many vertices of degree 4 are there?


Please help, it's much appreciated.
Let v1 be the number of vertices of degree 4 and v2 be the number of vertices of degree 5.
We know that v1+v2=16 and from handshake lemma we get that 4v1+5v2=70.

So you only need to solve the system of 2 linear equations
v1+v2=16
4v1+5v2=70

Solution is v1=10, v2=6.