Thread: Prove a graph doesn't exists

Hi,

I have to prove that a 3-connected graph with 7 edges doesn't exists. I guess I should prove this statement by contradiction, but I don't know how to begin. Any ideas?

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?

Whats nice here is that you can extend this argument to any number of edges E, and connectivity K. That is, if you have the numbers



N - number of nodes
E - number of edges
K - connectivity

then if


then there can not exist a graph with N nodes, E edges and K connectivity.

Perhaps one can make this argument stronger and prove the converse? Hmm...

Edit:
Actually with I thought about it a little and I think its an if and only if. I'd need to prove it but I think the statement

There exists a graph with N nodes E edges and K connectivity

is true. I showed the ==> direction above, and for the other way <== use the same argument as above to construct the graph with N nodes, E edges and K connectivity by taking the fully connected graph and deleting the edges such that no nodes degree drops below K, if the RHS is true then this should always be possible.

edit:

nevermind the converse is probably not true. ignore my thoughts on the converse, all I can guarantee is that the minimum degree >= K which is not enough to show K connectivity.