Quandaries and Queries


Name: Ali
Who is asking: Student
Level: Secondary

How can i find out {6,6,5,5,5,3,2}is not the sequence of the points of a simple graph,without drawing it?



Hi Ali,

Without drawing it explicitly??? Clearly you need 7 points and two of them are joined to all of the others. Think of the graph with them and the (adjacent) point of degree 2 removed. This leaves 4 points with degrees {3,3,3,1} which is easily seen to be impossible if you remove the point of degree 1.



Go to Math Central