Take the 2-minute tour ×
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.

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|improve this question
1  
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag; people will still help, so don't worry. Also, some people on this site consider the use of imperatives (show, prove, do etc.) rude. Consider editing you question –  Dennis Gulko Dec 1 '12 at 13:42
    
@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

1 Answer 1

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|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
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. –  Heisenberg Dec 2 '12 at 9:28

Your Answer

 
discard

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.