4
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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.

enter image description here

$\endgroup$
2
  • $\begingroup$ Thank you. It's a great solution. $\endgroup$ – walter Apr 12 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Joffan Apr 12 at 16:46
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – walter Apr 12 at 16:40
  • $\begingroup$ 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). $\endgroup$ – Misha Lavrov Apr 12 at 17:20
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – walter Apr 12 at 15:51
  • $\begingroup$ @walter The graphs should look like "sausages." Do it for something like 24 vertices. $\endgroup$ – Igor Rivin Apr 12 at 16:03
  • $\begingroup$ @MishaLavrov Different people's intuitions differ. $\endgroup$ – Igor Rivin Apr 12 at 16:36
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Apr 12 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.