1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

The following graph satisfy the requirment and it has 22 edges: enter image description here

$\endgroup$
  • 1
    $\begingroup$ That appears to meet the requirements for the graph (and has the needed 22 edges), but the OP didn't ask for the graph, they asked the easiest way to approach the problem. $\endgroup$ – T. M. Dec 8 '18 at 21:46
  • 1
    $\begingroup$ (It has 22 edges.) But more importantly: @T. M. I disagree, this is an important part of the proof. If you use the standard formula I referred to in my answer, it gives you that the only possible number of edges for such a graph is $22$. If you do not show such a graph (or prove it exists somehow), then theoretically speaking, it is possible that no such graph exists, in which case the answer to the question is: ANYTHING AT ALL. (Even "Brad Pitt" is a correct answer then.) However, once you show such a graph, the answer is $22$. Huge difference. $\endgroup$ – A. Pongrácz Dec 8 '18 at 22:36
  • 1
    $\begingroup$ @A. Pongrácz I agree with the need for the graph, my point was posting it without any hint as to how to find it doesn't help the OP to solve any similar problems. Beyond confirming what you already said. $\endgroup$ – T. M. Dec 9 '18 at 0:18
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\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.