Orientation of a bipartite graph

172 Views Asked by At

I need to determine whether the complete bipartite graphs $K_{n,m}$ with $n,m \ge 2$. Are orientable.

Am I correct in going about doing this by induction and using the fact that all of the complete bipartite graphs can be created using a number of circuits.

I am just unsure about how I go about proving this, I’m pretty sure that all are orientable by drawing a number of the graphs.

1

There are 1 best solutions below

0
On

If $n,m\geq 2$ then $K_{n,m}$ stays connected after the removal of one edge, hence $K_{n,m}$ has a strong orientation by Robbins' theorem.