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

3 Answers 3

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .