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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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
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: