6
$\begingroup$

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

1 Answers 1

7

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ó.)

  • 2
    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.2012-12-02