Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Could you give a brief definition of what a one-dimensional graph is? If I've guessed the definition right, I think you'll find that $L_1$ and $L_2$ are one-dimensional and the rest are not, but it would help to know exactly which definition you're using. –  Ilmari Karonen Feb 7 '12 at 14:43
    
By one-dimensional I mean a graph that can be depicted on a piece of paper and the edges do not meet.Thanks for your time!! –  thrasos Feb 7 '12 at 15:01
    
A piece of paper is usually considered two-dimensional. The definition you give sounds like that of a planar graph. Is that what you mean, or is it something else? –  Ilmari Karonen Feb 7 '12 at 15:08
    
Yes you are right!planar or non planar graph. –  thrasos Feb 7 '12 at 16:13

1 Answer 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)$.)

share|improve this answer
    
Or note that each of $\ell_3,\ell_4,\ell_5$ is adjacent to each of $r_1,r_2,r_3$. –  Gerry Myerson Feb 7 '12 at 23:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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