# Question on planar graphs

• Apr 8th 2009, 09:09 AM
titandude21
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.
• Apr 8th 2009, 10:35 AM
Opalg
Quote:

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 \$\displaystyle 2\bigl(\tfrac{5v}2\bigr)\geqslant3\bigl(\tfrac{3v} 2+2\bigr)\$.

Quote:

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 \$\displaystyle v\geqslant 3\$ vertices has at most 3v - 6 edges. The proof is the same as for the previous result: \$\displaystyle 2e\geqslant3f\$ together with \$\displaystyle v+f=e+2\$.