# An example of planar graph with maximal edges

Let $$G$$ be a graph on vertices $$v_1, v_2, . . . , v_n$$ such that $$v_iv_j$$ is an edge iff $$0 < |i − j| ≤ 3$$. Prove that $$G$$ is planar having $$3n − 6$$ edges.

Please get me started. Any help will be appreciated. Thanks. I know there will be $$3n - 6$$ edges, but I couldn't do the planar part.

Probably the easiest way to envisage the resulting graph is to visualize it in three dimensions as a polyhedron instead of a planar graph. Each added vertex is the top of a three-sided pyramid placed on an existing face (which face was added in the previous step, in fact).

And the graph of such a polyhedron projects to a sphere which maps to the plane.

• Thank you. It's a great solution. – walter Apr 12 at 16:42
• The graph suggests another visualization/justification without going 3D; each successive point from $v_4$ onwards is placed in an existing triangular region and connects to the vertices on the boundary, which also makes the triangular region for the next point placement. – Joffan Apr 12 at 16:46

Try proving that the graph can be drawn by induction: given a suitably chosen drawing of the $$n$$-vertex $$G$$, it can be extended to the $$(n+1)$$-vertex $$G$$ by adding a vertex $$v_{n+1}$$ adjacent to $$v_{n-2}, v_{n-1}, v_n$$.

For this to be possible, $$v_{n-2}, v_{n-1}, v_n$$ all have to lie on the same face of the $$n$$-vertex graph. Actually, since they are all adjacent, and all faces of $$G$$ are triangles, they must be a face of the $$n$$-vertex graph.

For simplicity, we may assume that this face is the external face, which makes adding $$v_{n+1}$$ easy. So we have the strengthened claim:

Claim. For all $$n\ge3$$, $$G$$ has a plane embedding in which the external face is a triangle with vertices $$v_{n-2}, v_{n-1}, v_n$$.

Try to prove this claim by induction.

• Thank you very much. This is a very nice solution. I'd like to say only one small thing viz. I think the claim is unnecessary. For even if the face is not external, we can add the $(n+1)$-th point on interior of that face. Then also the proof works. Right? – walter Apr 12 at 16:40
• If the face is not external, the proof still works. However, not all triangles are faces, so we should still prove "$G$ has a plane embedding in which $v_{n-2}, v_{n-1}, v_n$ are on the same face", which is a stronger claim than "$G$ has a plane embedding". I'm just making this face the external face for concreteness (but once you have an embedding, you can make any face the external face). – Misha Lavrov Apr 12 at 17:20

First compute the edge count. What is the degree of $$v_i?$$ It depends on $$i.$$ As for showing the graph is planar, draw pictures for small $$n,$$ and see if you can generalize what they look like.

• Degree of $v_i$ will be at max $6$. Can you please give a little more hint on how to prove the planar part? I drew smaller graphs. – walter Apr 12 at 15:51
• @walter The graphs should look like "sausages." Do it for something like 24 vertices. – Igor Rivin Apr 12 at 16:03
• @MishaLavrov Different people's intuitions differ. – Igor Rivin Apr 12 at 16:36
• If you are sure that you have the right graph, then I am not at all criticizing; I was only worried that you had the wrong graph in mind. – Misha Lavrov Apr 12 at 17:22