# How to prove that if a graph is planar and $v+f-e=2$, then the graph is connected?

I'm having trouble with this problem from Trudeau's Introduction to Graph Theory and would appreciate any hints.

Prove this partial converse of Euler's Formula: if a graph is planar and $v+f-e=2$, then the graph is connected.

Here's what I've tried so far:

The problem asks me to prove a statement of the form $A \wedge B \implies C$, where:

• $A$ means the graph is planar
• $B$ means $v+f-e=2$
• $C$ means the graph is connected

It seems difficult to prove $C$ for any graph, so I formed the contrapositive statement: If a graph is disconnected, then either the graph is nonplaner or $v+f-e \neq 2$. So now I'm trying to prove that $\neg C \implies (\neg A \vee \neg B)$.

I drew example graphs that are disconnected, planar, and in all the examples I came up with, $v+f-e \neq 2$. This suggests that $\neg C \wedge A \implies \neg B$. If I could prove this, then I believe this is equivalent to a proof of $\neg C \implies (\neg A \vee \neg B)$, which is in turn equivalent to a proof of $A \wedge B \implies C$. But I am stuck here.

Is the contrapositive approach even a helpful one? Are there any other tips on how I might approach the proof?

-
Excellent book, by the way. The original title was Dots and Lines. – Gerry Myerson Dec 7 '11 at 3:12

Hint If a graph is planar, then each component $G_i$ is planar and then
$$v_i+f_i-e_i=2 \,.$$