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?