# Math Help - Question on planar graphs

1. ## Question on planar graphs

i'm stuck on this proof:
prove that any planar graph with very vertex having degree 5 has at least 12 vertices.

a planar graph G with all v vertices with degree 5 has 5v/2 edges
Euler's formula states that vertices - edges + faces = 2
so there are 3v/2 + 2 faces in G

I'm not sure how to get the # of faces in G, or whether it's relevant to the problem.

also this one:
show that a plane graph with v>=3 vertices has at most 2v - 4 edges

any help is appreciated.

2. Originally Posted by titandude21
prove that any planar graph with very vertex having degree 5 has at least 12 vertices.

a planar graph G with all v vertices with degree 5 has 5v/2 edges
Euler's formula states that vertices - edges + faces = 2
so there are 3v/2 + 2 faces in G

I'm not sure how to get the # of faces in G, or whether it's relevant to the problem.
Every face must have at least 3 edges, and each edge is shared between 2 faces. So $2\bigl(\tfrac{5v}2\bigr)\geqslant3\bigl(\tfrac{3v} 2+2\bigr)$.

Originally Posted by titandude21
also this one:
show that a plane graph with v>=3 vertices has at most 2v - 4 edges
Not true. For example, the graph of a tetrahedron has 4 vertices and 6 edges (see attached image). What is true is that a plane graph with $v\geqslant 3$ vertices has at most 3v - 6 edges. The proof is the same as for the previous result: $2e\geqslant3f$ together with $v+f=e+2$.