Problem 1D: The complete bipartite graph {K_{n,m}} has { n+m} vertices {a_{1},\ldots ,a_{n}} and {b_{1},\ldots ,b_{m},} and as edges all {mn} pairs {\left\{ a_{i},b_{j}\right\} .} Show that {K_{3,3\text{ }}}is not planar.

Solution: Euler’s formula states that for a drawing of a connected planar graph on the plane, {f-e+v=2}, where {f,e} and {v} are, respectively, the numbers of faces, edges, and vertices. If {K_{3,3}} is planar, {f-9+6=2,} thus {f=5.} On the other hand, each face in a bipartite graph has at least four border edges, and each edge shares two faces. Hence there would be at least {\frac{4f}{2}=10} edges in the graph, contradicts to the number of edges of {K_{3,3}.}

Notes: By the hints of problem 1D, the author tells to show there are only one drawing in some sense if we omit one point of {K_{3,3}}, and just considering the remaining 6 edges. But in what sense? I am curious for the exact explanation.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: