Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 6 down vote accepted

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

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

share|improve this answer
    
Thanks for the quick and helpful hint! –  Andrew Liu Dec 6 '11 at 21:01
    
@AndrewLiu Just be carefull with the fact that you will count the infinite face for each component ;) –  N. S. Dec 6 '11 at 22:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.