Planar Graphs!

[Reb]

Consider the sequence of graphs \(\displaystyle (L_n)\) consisting of nodes \(\displaystyle \{l_1,\ldots\l_n\}\cup\{r_1,\ldots,r_n\}\) and edges \(\displaystyle \{E_{ij}, \ i\geq j\}\) connecting \(\displaystyle l_i\) to \(\displaystyle r_j\) respectively.


Which of the graphs \(\displaystyle (L_n)\) are planar? Portray these on the plane.

 

[SlipEternal]

Consider the sequence of graphs \(\displaystyle (L_n)\) consisting of nodes \(\displaystyle \{l_1,\ldots\l_n\}\cup\{r_1,\ldots,r_n\}\) and edges \(\displaystyle \{E_{ij}, \ i\geq j\}\) connecting \(\displaystyle l_i\) to \(\displaystyle r_j\) respectively.


Which of the graphs \(\displaystyle (L_n)\) are planar? Portray these on the plane.

What sort of assistance do you need? Do you want us to just tell you the answer? My guess? \(\displaystyle L_0, L_1, L_2\text{ and } L_3\) are definitely planar. \(\displaystyle L_4\) is possibly planar. \(\displaystyle L_n, n\ge 5\) are not planar.

 

[pka]

Consider the sequence of graphs \(\displaystyle (L_n)\) consisting of nodes \(\displaystyle \{l_1,\ldots\l_n\}\cup\{r_1,\ldots,r_n\}\) and edges \(\displaystyle \{E_{ij}, \ i\geq j\}\) connecting \(\displaystyle l_i\) to \(\displaystyle r_j\) respectively. Which of the graphs \(\displaystyle (L_n)\) are planar? Portray these on the plane.

It seems to me that from the above description that \(\displaystyle L_n=K_{n,n}\).
i.e. A complete bipartite on \(\displaystyle 2n\) vertices.
If that is correct \(\displaystyle L_3\) cannot be planar.
As matter of fact that is Kuratowski's theorem on planar graphs.
That is the original three utilities one finds in many elementary textbooks.s

 

[SlipEternal]

It seems to me that from the above description that \(\displaystyle L_n=K_{n,n}\).
i.e. A complete bipartite on \(\displaystyle 2n\) vertices.
If that is correct \(\displaystyle L_3\) cannot be planar.
As matter of fact that is Kuratowski's theorem on planar graphs.
That is the original three utilities one finds in many elementary textbooks.s

That is not my reading. \(\displaystyle L_3 = \left\{\{l_1,l_2,l_3,r_1,r_2,r_3\},\{l_1r_1,l_2r_1,l_2r_2,l_3r_1,l_3r_2,l_3r_3\}\right\}\). That does not look like \(\displaystyle K_{3,3}\) to me. \(\displaystyle K_{3,3} = \left\{\{l_1,l_2,l_3,r_1,r_2,r_3\},\{l_1r_1,l_1r_2,l_1r_3,l_2r_1,l_2r_2,l_2r_3,l_3r_1,l_3r_2,l_3r_3\}\right\}\)

 

[daon2]

L_3 is constructible on a piece of paper. I can't find a way for L_4 (the last vertex always ends up by itself), and I think L_n, n>= 4, would have L_4 as a subgraph it should be enough to show that L_4 is not.

 

[SlipEternal]

\(\displaystyle \begin{tabular}{c c c c c c c c c}
& & / & - & - & - & l_3 & - & \backslash \\
& & \| & & & & \| & & \| \\
l_1 & - & r_1 & - & l_2 & - & r_2 & & r_3 \\
& & \| & & & & \| & & \| \\
& & \backslash & - & - & - & l_4 & - & / \\
& & & & & & \| & & \\
& & & & & & r_4 & &
\end{tabular}\)

I am not sure how to draw graphs in Latex, so I hope this is understandable. The double vertical lines should only be single vertical lines, but they didn't show up correctly when I tried that.