Question : A graph has 11 vertices classified as follows: six vertices have degree 3, one vertex has degree 4, two have degree 5 and two have degree 6. How many edges does this graph have?
I started to draw the graph but I could not fit with the requirements. I draw first the vertex with largest degrees (6, after 5 etc) but at the end it does not work.
What is the easiest way to approach this problem?
On
Ok, this problem felt like it would have some good theory behind it and it does. The general problem, called the Graph realization problem, is given a degree sequence, does a simple graph exist with that degree sequence. That article discusses two known methods, the Havel–Hakimi algorithm, and the other is following the Erdős–Gallai theorem. There are a number of posts on SE about the Havel–Hakimi algorithm. If you follow HH, it also shows how to construct a graph with the given degree sequence.
On
You can think all the vertices are seperate and has connectible branches as many as their degree's. Then start counting.
For example: One of the six degree vertex will make six edges. Count'em as six edges and delete six other connectible branch from other nodes. After all you will left with one 4 degree vertex and it will make 2 edges. Total number of edges will be 22.enter image description here
Number of edges multiplied by $2$ equals to the total sum of degrees. (Think about it, easy double counting argument.) Of course, it is important that the conditions be consistent, so you do need to prove that such a graph exists. (I.e., it was a good idea to try to draw one.)