1
$\begingroup$

A graph G has 50 edges and 30 vertices. Each vertex in G has either degree 3 or degree 4. How many of the 30 vertices in G have degree 3 and how many have degree 4?

3 Answers 3

4

If there are 50 edges, the sum of the degrees of all the vertices should be twice that number at 100. Call the number of vertices of degree 3 $x$. There are then $30-x$ vertices of degree 4.

I get a sense this might be homework, so I'll leave the algebra of solving for $x$ to you.

4

as we know that the sum of all the degrees is equal to twice the number of edges, u may take number of vertices of degree 3 as 'x' and rest as 30-x. and you will get number of vertices of degree 3 as an even number since we know that total number of vertices with odd degree are even in number in any graph

0

Suppose there are $x$ vertices of degree $3$ and $y$ vertices of degree $4$. The number of vertices is: $x+y=30.$

The Handshaking Lemma asserts that the sum of the degrees is twice the number of edges. Hence $3x+4y=100.$

This gives a system of linear equations which can be solved to give $x=20$ and $y=10$. These parameters are realised e.g. by the following graph:

Graph with <span class=20 vertices of degree $3$ and $10$ vertices of degree $4$">