# 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. Apr 12, 2021 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. Apr 12, 2021 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? Apr 12, 2021 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). Apr 12, 2021 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. Apr 12, 2021 at 15:51
• @walter The graphs should look like "sausages." Do it for something like 24 vertices. Apr 12, 2021 at 16:03
• @MishaLavrov Different people's intuitions differ. Apr 12, 2021 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. Apr 12, 2021 at 17:22