0
$\begingroup$

I'm having some trouble with planar graphs. Two questions I was stuck on were:

  1. Prove that each planar graph on $n \gt 3$ vertices will have a minimum of $4$ vertices of degree $5$ at most.

  2. Let's say you are provided a planar graph on $17$ vertices and that there is a drawing of such a graph with $17$ faces (countries). Prove that such a graph has vertex with degree $3$ or less.

$\endgroup$

2 Answers 2

1
$\begingroup$

The tool you want is the Euler characteristic:

http://en.m.wikipedia.org/wiki/Euler_characteristic

For a planar graph, $V+F=E+2$. Don't forget to count the "outside" as a face.

$\endgroup$
3
  • $\begingroup$ Hm, interesting. So to prove the above two questions, do I just prove it completely... algebraically? Sorry - I don't have a lot of time at the moment, I will be sure to look at the Euler Characteristic more in detail when I have time tonight/tomorrow. $\endgroup$
    – Jay C
    Commented Nov 19, 2013 at 0:05
  • $\begingroup$ Pretty much, yes. In fact, one of the proofs is described on that page. ;-) $\endgroup$
    – apt1002
    Commented Nov 19, 2013 at 0:23
  • $\begingroup$ Sorry, I don't entirely understand how I'm meant to incorporate the degree into the euler characteristic. $\endgroup$
    – Jay C
    Commented Nov 25, 2013 at 6:58
0
$\begingroup$

I ended up using a proof by contradiction. For (1), I showed multiple cases. For (2), I solved for the number of edges then assumed to the contrary that all vertices are of degree 4.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .