1
$\begingroup$

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?

  • 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.2010-11-30

2 Answers 2

6

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.

  • 1
    Yes, he is saying that. See also my comments $f$or another (perhaps slightly more rigorous, if only because proofs by pictures are frowned upon in some circles) proof.2010-11-30
0

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