1
$\begingroup$

A graph $L_n$ has vertices $V=\{l_1,l_2,\dotsc,l_n\}\cup\{r_1,r_2,\dotsc,r_n\}$ and edges $E=\{(l_i,r_j): i \ge j\}$ .

Which of these graphs $L_1$, $L_2$, etc. are planar and which are not? For those that are planar, give an appropriate depiction (scheme) and for the others write the proof.

  • 0
    Yes you are right!planar or non planar graph.2012-02-07

1 Answers 1

1

First of all, note that a graph which contains a non-planar subgraph obviously cannot be planar: adding new vertices and edges to an already non-planar graph can't possibly make drawing it in a plane without intersections any easier.

In your case, $L_i$ is a subgraph of $L_j$ for all $j > i$; thus, if we can show that $L_i$ is non-planar for some $i$, we've also shown it for all $j > i$. Conversely, showing that $L_i$ is planar implies that $L_j$ is also planar for all $j < i$.

It should not be particularly hard to draw the graphs from $L_1$ up to $L_4$ on paper without intersections, thereby demonstrating that they're planar.

As for $L_5$, recall Wagner's theorem: A finite graph is planar if and only if it does not have $K_5$ (the complete graph on five vertices) or $K_{3,3}$ (the complete bipartite graph on six vertices) as a minor. Can you find either of these graphs as a minor in $L_5$? (Hint: try contracting edges of the form $(l_i, r_i)$.)

  • 0
    Or note that each of $\ell_3,\ell_4,\ell_5$ is adjacent to each of $r_1,r_2,r_3$.2012-02-07