To prove this is suffices to show that with 7 edges, there must always be a node with degree 2, or less.

The strategy to show this is as follows. First, consider a fully connected graph of 5 nodes. (The reason we consider 5 not 4 is because fully connected graph with 4 nodes has 6 edges.) There are edges in this graph. We can construct *any* graph with 5 nodes and 7 edges by removing 3 edges from this graph.

Consider removing the 3 edges (u,v),(w,x),(y,z). I claim that then at least two of u,v,w,x,y,z are equal. To see this note we have 5 vertices, and 6 of u,v,w,x,y,z. Thus one of these must be the same as at least one other by the pigeon hole principle. In the fully connected graph, each node has degree exactly 4. Since there is one repeated node in (u,v),(w,x),(y,z) (lets say u without loss of generality) then it must be that degree of u is 4 - 2 = 2.

Now consider the general case. Suppose we have N vertices and 7 edges. There are edges in the fully connected graph, and we can construct any graph with N edges and 7 edges by deleting edges. Now by the same pigeon hole argument as above, there is a node that drops by

degree. Since each node has N-1 degree is suffices to show that

You can actually show that for this is always true, since

and for it is easy to show that

.

This means that the only case that remains for you to verify is with 6 nodes and 7 edges. Can you do that one yourself?