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.

On a 2D plane, how to construct a graph with 7 vertexes and 21 edges? I tried various combination but couldn't seem to draw that kind of contrived graph on a paper.

But my understanding is that it is possible. So anyone can help me with it?

share|improve this question
    
Sorry, I don't see why the link you give shows that this is possible. In fact, assuming you don't allow edges to start and end at the same places, then I'm pretty sure that this would have to be a complete graph, and I'm also pretty sure that the complete graph on 5 (?) vertices is already nonplanar. But I don't know much about this stuff, so I could very easily be wrong. –  Aaron Mazel-Gee Nov 30 '10 at 7:10
1  
Err... I'm pretty sure that would give an impossible simplicial decomposition of $S^2$, which is what you get when you compactify the plane. Let's see: there are 5 vertices and 10 edges, so there need to be 7 faces (since $\chi(S^2)=2$). But every face has at least 3 edges, which means we'd need at least 21 edges when we've double-counted (since every edge touches exactly 2 faces), meaning we need at least 11 edges. This is a contradiction. –  Aaron Mazel-Gee Nov 30 '10 at 7:32
1  
Yes. Assuming what I assumed above (and actually also that no edges start and end at the same vertex), it follows from easy combinatorics that this would have to be the complete graph on 7 vertices, which contains as a subgraph the complete graph on 5 vertices. If the latter isn't embeddable in the plane, then certainly the former isn't either. –  Aaron Mazel-Gee Nov 30 '10 at 8:39
1  
The complete graph on 5 vertices is indeed nonplanar; see Kuratowski's Theorem: en.wikipedia.org/wiki/Kuratowski%27s_theorem –  Hans Lundmark Nov 30 '10 at 8:59
1  
Right. I knew this had a name (which I had forgotten), but it's easy enough to prove that $K_5$ is nonplanar that I thought it'd be nice to do it by hand. –  Aaron Mazel-Gee Nov 30 '10 at 9:09
show 3 more comments

2 Answers

up vote 5 down vote accepted

My guess is you're after $K_7$ drawn on the torus; see http://www.amotlpaa.org/math/k7torus.html

To answer you question as to why $K_5$ is not planar: If a complete graph is planar, then for every $K_3$ subgraph, either every vertex (that's not part of the $K_3$) is inside the $K_3$ or outside the $K_3$ (otherwise there's a crossing edge from outside to inside the $K_3$).

So, if we attempt to draw $K_5$ vertex-by-vertex, then we first draw a triangle $K_3$. We can place the 4-th vertex either inside or outside of the triangle. In either case, the drawing obtained will look like:

alt text

Now, wherever you put the 5-th vertex, you will form some $K_3$ subgraph for which the other two vertices are not both inside and not both outside.

share|improve this answer
    
are you saying that my graph above must be non-planar? –  Graviton Nov 30 '10 at 8:02
1  
Yes, he is saying that. See also my comments for another (perhaps slightly more rigorous, if only because proofs by pictures are frowned upon in some circles) proof. –  Aaron Mazel-Gee Nov 30 '10 at 8:43
add comment

Although the software below does not allow one to check for planarity you might find it useful in seeing drawings of graphs (not typically drawn in the plane) with a small number of vertices and specified number of edges:

http://www.gfredericks.com/sandbox/graphs/browse

share|improve this answer
add comment

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.