3

I know that someone has already asked the same question here, but there is no solution for part two of the question. And I'm interested in the second part. Here the question:

Suppose we build $S^2$ from a finite collection of polygons by identifying edges in pairs. Show that in the resulting CW complex structure on $S^2$, the 1-skeleton cannot be the graph $K_{3,3}$

I know that the Euler characteristic of the spere $S^2$ is 2. Since the graph has 6 vertices and 9 edges, we have 5 polygons ( since 6-9+x=2 so x=5). So we habe in total 5 polygons with 18 edges (since always two edges are identified). Now I don't know how to find a contradiction. For me it doesn't look so easy. For example I know that the triangular prism has exactly 5 sides, 6 vertices and 9 edges. But obviously the graph is not the one skeleton of this prism.

Community
  • 1
Rungo
  • 490
  • K3,3 is not a planar graph and so cannot be embedded in a disc. Since S^2 is formed by gluing two discs along their boundary, it's skeleton can not be K3,3. – Hesky Cee Feb 04 '14 at 21:57

1 Answers1

4

I am assuming that you know that $K_{3,3}$ is not planar.

Recall that a graph is planar if it can be embedded in $D^2$. Now suppose by contradiction that $K_{3,3}$ is a 1-skeleton of $S^2$. Remove a small open disc in the interior of a face the sphere. What is left is a disc which implies $K_{3,3}$ is planar.

Alternatively: (This answer is due to your comment.) If $K_{3,3}$ is the 1-skeleton of a sphere, use $v-e+f=2$ to show $f=5$.Take a look at graph of $K_{3,3}$. Show that the least number of edges that bound a face is $4$. Since there are $5$ faces, we have atleast $5\times4$ edges. Using the fact that any edge bounds at most two faces, deduce that we have $e\geq10$. Does this agree with value of $e$ you stated with?

Hesky Cee
  • 452
  • Thank you very much for your answer! In the lecture we never talked about planar graphs. We just discussed Euler charakteristic. Why does a graph need to be planar to be a one skeleton of a sphere? How can I prove that the graph is planar? Is there a solution without using more than just Euler characteristic? – Rungo Feb 04 '14 at 22:21
  • For a connected planar simple graph with v vertices and e edges, and no triangles, e ≤ 2v - 4. If you can show this, then it is easy to see why K3,3 is not planar. – Hesky Cee Feb 04 '14 at 22:41
  • Hint: Use euler characteristic of a graph and the handshaking lemma. I'm sure you have these tools. – Hesky Cee Feb 04 '14 at 22:43
  • Thank you very much for your answers. Now I understand it. You helped me a lot! – Rungo Feb 05 '14 at 07:06