Complete bipartite graph from 2 to m points

103 Views Asked by At

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies above and below the first one

2

There are 2 best solutions below

2
On BEST ANSWER

Important fact: You don't need to draw bipartite graphs with all points in one set "near" each other in any sense. Mathematically, the graph is just determined by the set of vertices and the information about which are joined by lines. Whether or not it's bipartite is unaffected by how we draw it. All that matters is that it can be divided into two sets of vertices (which may be separated in space), neither of which has any internal edges.

Hint: Put the $m$ points in a straight line. Where can you put the two points to make it easy to draw all the lines without intersection?

0
On

Draw $m$ points in a line, one above and one below.