Question

Let p>=3 and G be a planar graph with p vertices and 3p-7 edges. Prove G is connected.

A connected graph is a graph in which for any 2 vertices there is a path connecting them.

Answer 1

A graph is planar if you can draw it in a plane so that edges only intersect at their ends and no two vertices coincide

Answer 2

Perhaps it would be possible to argue by mathematical induction...

Answer 3

The first case is p = 3. Then, we have 3 vertices and 3(3) - 7 = 2 edges. It is fairly obvious that G is connected in this case.

Answer 4

I'm not especially good with proofs by induction. I can see that the base case is true however.

Answer 5

Yeah, idk... the induction hypothesis would be suppose that G is connected for p = k with 3k - 7 edges.

Answer 6

Then, for the (k+1)st case, we would have k+1 vertices and 3(k+1)-7 = 3k-7 + 3 edges.

Answer 7

We claim that G is connected. Observe that the first k vertices can be connected using the first (3k-7) edges by the induction hypothesis. So this "subgraph" is connected. Then, we have 1 vertex left and 3 edges remaining. But we can easily attached this 1 vertex to the connected "subgraph" with the 3 edges. Hence, p = k+1 is also connected.

Answer 8

It seems to work, but I'll be the first to admit that I don't know much graph theory. :P

Answer 9

I think the statement that "we can easily attach this 1 vertex to the connected 'subgraph'" is probably a bit fuzzy. This probably has something to do with a planar property.

Answer 10

A different approach might be to use the "evenness" or "oddness" of the vertices. I'm literally just throwing ideas out here.

Answer 11

That seems like it could work, but I think the problem is whether or not adding the edges would destroy the planarity

Answer 12

Yeah, but the thing to keep in mind is that the planarity is given... it's the connectivity that is the concern.

Answer 13

Not sure, this one's got me. Good luck!

Answer 14

Thanks for your help anyways!