4
$\begingroup$

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?

  • 0
    Excellent book, by the way. The original title was Dots and Lines.2011-12-07

1 Answers 1

7

Hint If a graph is planar, then each component $G_i$ is planar and then

$v_i+f_i-e_i=2 \,.$

  • 0
    @AndrewLiu Just be carefull with the fact that you will count the infinite face for each component ;)2011-12-06