# planar graphs and vertices of degree $5$

I am studying for my final exam and the prof suggested this problem.. so I'd really appreciate some help!! Thanks!

Let $G$ be non-null, simple and planar, with no vertex of degree less than or equal to $4$.
a) Is it true that $G$ must have two vertices of degree $5$ which are joined by a path of length $< 10^6$?
b) Is it true that if the number of vertices of $G$ is greater than $10^6$ then $G$ has greater than or equal to $13$ vertices of degree $5$?

-
@Dennis While the comment applies in part, the last sentence in your comment does not apply. I'd try to tailor this "standard comment" to the particular question at hand, omitting parts that do not apply, e.g. –  amWhy Dec 1 '12 at 14:14

Part a.)

Not True. Start with the graph of the icosahedron - a 5-regular planar graph, furthermore a triangulation. Then you subdivide all segments by adding a vertex. Connect the new vertices of each face, by a cycle. The new vertices have degree 6. The old degree-5 vertices have now distance 2. Now you repeat this construction. Every time you double the distance between the original degree-5 vertices. So you can make the distance between these vertices arbitrarily long.

The picture shows the first step of the construction.

Part b.)

Not true. By Euler's formula and the handshaking lemma you can show that there have to be at least 12 degree-5 vertices. But this is indeed enough. Here is a construction that shows that there are infinitely large planar graphs with 12 degree-5 vertices and all other vertices having degree 6: Take a triangular $m\times 6$ grid and wrap it around by identifying the $m$-vertex border. Then insert a pyramid in each of the two remaining pentagons. The graph from part a would be also an example.

(Picture taken from the phd thesis of Ares Ribó.)

-
Sorry... I'm pretty stuck trying to show this with Euler's formula.. Is it possible you could help me out a bit more? –  madams Dec 1 '12 at 21:08
Using Euler's formula and a double you can show that every maximal planar graph (= every face is a triangle) has $3 n -6$ edges $m$. Use this and the fact that $2m=3 n_3+4 n_4$ (for $n_i$ being the number of degree-i vertices). –  A.Schulz Dec 1 '12 at 21:15
In your last sentence you mention 2m = 3n3 + 4n4, but in this case there are vertices of degree less than 4. And in Euler's formula, how does one deal with "f", the number of faces? Thanks.. and sorry for not understanding! –  madams Dec 1 '12 at 21:36
That was a typo it has to be $5n_5 + 6n_6 =2m$. You get rid of the $f$ in Euler's formula by noticing, when all faces are triangles: $3f=2m$, since every edge is incident to two faces. –  A.Schulz Dec 2 '12 at 6:52
I don't see how your counterexample in part a) disproves the statement. The question asks if there exist TWO vertices of degree 5 which are connected by a path, not if EVERY vertex of degree 5 is connected to each other by a path. –  Heisenberg Dec 2 '12 at 9:28