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?

  • 0
    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.2010-11-30
  • 0
    *complete graph on 5 (?) vertices is already nonplanar*, any reason you say so?2010-11-30
  • 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.2010-11-30
  • 0
    @Aaron, are you saying that it is not possible to construct a planar graph with 7 vertex and 21 edges on a 2D plane?2010-11-30
  • 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.2010-11-30
  • 0
    And if you're asking questions that force a particular number of edges to be in the graph you're attempting to embed, then certainly you want to make those two assumptions about your edges.2010-11-30
  • 1
    The complete graph on 5 vertices is indeed nonplanar; see Kuratowski's Theorem: http://en.wikipedia.org/wiki/Kuratowski%27s_theorem2010-11-30
  • 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.

  • 0
    are you saying that my graph above must be non-planar?2010-11-30
  • 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.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