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?
|show 3 more comments|
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.
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: