Tuesday, December 9, 2014

Is it possible to make a graph with four vertices of degree 2, 3, 4, and 2?

Nope. 


Every edge connecting
vertices has two endpoints.  So if you start with a bunch of unconnected vertices, they
are all degree 0 and the sum of the degrees is 0, an even number.  If you add an edge
between two of those vertices, now you have two vertices of degree 1 and everything else
has a degree of 0, so now the sum of the degrees is 2, again an even number.  If you
added the edge so that it had both endpoints at the same vertex, you'd have one vertex
with degree 2 and everything else degree 0, so the sum of the degrees is still 2.  Every
time you add another edge, the sum of the degrees goes up by 2 more.  So the sum of the
degrees is always an even number. 


In the problem you pose,
the sum of the degrees is 11, so you'd need 5 1/2 edges, and there is no way to put half
an edge into your graph.

No comments:

Post a Comment

What is the meaning of the 4th stanza of Eliot's Preludes, especially the lines "I am moved by fancies...Infinitely suffering thing".

A century old this year, T.S. Eliot's Preludes raises the curtain on his great modernist masterpieces, The Love...