Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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.

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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