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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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 $20$ vertices of degree $3$ and $10$ vertices of degree $4$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.