How many nodes of each degree are there in this graph?

  • Thread starter r0bHadz
  • Start date
  • #1
194
17

Homework Statement:

A graph has 12 edges and 6 nodes, each of which has degree of 2 or 5. How many nodes
are there of each degree?

Relevant Equations:

handshake theorem.
2m = summation of degree of each vertice where m = # of edges
there must be an even number of vertices of odd degree, and from the handshake theorem, 2m = 2(12) = 24

the only way we can get this from 6 vertices using 2 and 5 is:

4 vertices of degree 5, 2 vertices of degree 2

does this seem correct??
 

Answers and Replies

  • #2
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
If we denote with ##x## the number of nodes with degree ##2## and with ##6 - x## the number of nodes with degree ##5## then according to the theorem you say, you have a simple equation of the first degree in ##x##.
Its solution gives what is asked.
 
  • Like
Likes WWGD
  • #3
194
17
If we denote with ##x## the number of nodes with degree ##2## and with ##6 - x## the number of nodes with degree ##5## then according to the theorem you say, you have a simple equation of the first degree in ##x##.
Its solution gives what is asked.

So do I just plug and chug to find out? It seems like 4 of degree 5 and 2 of degree 2 meets the requirements?
 
  • #4
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
So do I just plug and chug to find out? It seems like 4 of degree 5 and 2 of degree 2 meets the requirements?
I would say yes, it seems so, but you must first form the equation and then solve it, in order to see it.
 

Related Threads on How many nodes of each degree are there in this graph?

  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
6
Views
2K
Replies
2
Views
1K
Replies
4
Views
3K
Replies
9
Views
843
Replies
18
Views
4K
  • Last Post
Replies
7
Views
1K
Replies
7
Views
3K
Replies
4
Views
446
Top