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.
On
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.
On
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.
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.