Show by finding an orientation on each that the complete gra

Show, by finding an orientation on each, that the complete graph K_n (n greaterthanorequalto 3) and the complete bipartite graph K_r, s (r, s greaterthanorequalto 2) are orientable.

Solution

A strongly connected orientation can be found using the depth-first search tree. Orient each edge in the tree from smaller label to larger label, and each edge not in the tree from larger label to smaller label.

A complete graph K_n has both Hamiltonian path and Hamiltonian cycle. Any Hamiltonian graph is orientable. If a graph is Hamiltonian, and the Hamiltonian cycle is oriented consistently in one direction, then there is a directed path from any vertex to any other vertex around the Hamiltonian cycle. (Alternately, a Hamiltonian graph must be connected, and have no bridges.)

As for the simple orientation, If you let the vertices be {u₁,u₂,...,u_r} and {v₁,v₂,...,v_s}.

Then a simple orientation would just be \"Let the direction of uivjuivj start from uiui and end with v_j for all 1ir,1js\".

For a strong orientation case, a valid solution would be \"Let the direction of uivjuivj start from u_i and end with v_j for all 1ir,1js, where i+j is even and start from v_j and end with u_i where i+j is odd.\".

To show this is a valid solution,

(1) Consider two arbitrary vertices from different components, u_i,v_{j ,} if i+j is even then u_iv_j would be a path from u_i to v_j, if i+j is odd then u_iv_j+1u_i+1v_j (If i=r change i+1 to i1 and if j=s change j+1 to j1) would be a path from u_i to v_j. Similarly, if i+j is even then v_ju_i is a path from v_j to u_i and if i+j is odd then v_ju_i+1v_j+1u_i (change the +1 to 1 for i=r or j=s) would be a path from v_j to u_i.

(2) Consider two arbitrary vertices from the same component, say u_i,u_k. Then from the previous case we know there exist a path p₁ from u_i to v₁ and a path p₂ from v₁ to u_k so p₁p₂ would be a path from u_i to u_k.