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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 4 down vote accepted

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. enter image description here

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.

enter image description here

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

share|cite|improve this answer
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

Your Answer


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.