# Construct a Graph with 7 Vertex, 21 Edges on 2D Plane

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?

-
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
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
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
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
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

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:

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.

-
are you saying that my graph above must be non-planar? – Graviton Nov 30 '10 at 8:02
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

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:

-