# What is the automorphism group of a complete bipartite graph?

Let $$m, n \in \mathbb{N}$$ with $$m \ne n$$. Determine the automorphism group of the complete bipartite Graph $$\mathcal{V}_{m,n}$$.

Some definitions: A complete bipartite graph is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $$U$$ and $$V$$, that is every edge connects a vertex in $$U$$ to one in $$V$$. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

My idea: In need to find an appropriate characterization of the larger set in the bipartite decomposition, but I am not sure.

An old exam question I am looking at to learn for my upcoming discrete math exam. I unfortunately am not sure what to do. Thanks in advance!

Are you familiar with graph automorphisms? We have a labelled graph, and permute its labels using some permutation $$\alpha$$: if the result is the same graph (i.e., vertices are adjacent in the permuted graph if and only if they are adjacent in the original graph) then $$\alpha$$ is an automorphism.

So in the above graph, if we swap the labels $$u_1$$ and $$u_2$$, then...

...the graph remains the same ($$u_1$$ and $$u_2$$ are both adjacent to $$v_1$$, and $$u_1$$ and $$u_2$$ are not adjacent); the permutation which swaps $$u_1$$ and $$u_2$$ is an automorphism.

But if we swap the labels $$u_1$$ and $$v_1$$ in our original graph, then...

...the graph does not remain the same ($$u_1$$ and $$u_2$$ are adjacent after applying this permutation); the permutation which swaps $$u_1$$ and $$v_1$$ is not an automorphism.

An example of a complete bipartite graph is (we can label the vertices however we like; usually one side is $$\{u_i\}$$ and one side is $$\{v_i\}$$):

The key observation we're meant to make here is: How many neighbors do the vertices have? (I.e., vertex degree.)

Vertex degree is an example of an invariant: if we apply an automorphism which maps a vertex a to vertex b then a and b have the same degree. (Otherwise it wouldn't be an automorphism---vertex a couldn't have the same adjacencies afterwards.) The contrapositive of this is: if vertex u and vertex v do not have the same degree, then no automorphism maps u to v.

(While it's true that bipartite graphs don't have odd-length cycles, it's not useful for this problem.)

So...

• What are the vertex degrees in $$U$$? (I.e., how many neighbors do vertices in $$U$$ have?)
• What are the vertex degrees in $$V$$? (I.e., how many neighbors do vertices in $$V$$ have?)
• Why does this imply automorphisms do not permute vertices in $$U$$ to vertices in $$V$$?
• Provided we permute vertices in $$U$$ to vertices in $$U$$ and vertices in $$V$$ to vertices in $$V$$, do we always get an automorphism?
• Bonus question: What if $|U| = |V|$? Jul 4 at 17:51

An automorphism of the complete bipartite graph $$\mathcal{V}_{m,n}$$ with $$m\neq n$$ must permute the vertices of each side of the bipartite graph independently. Therefore we can write an automorphism as $$(\phi,\psi)$$ were $$\phi$$ permutes $$m$$ vertices and $$\psi$$ permutes $$n$$ vertices. Writing two automorphisms as $$(\phi_1,\psi_1)$$ and $$(\phi_2,\psi_2),$$ their composite will be given by $$(\phi_1\circ \phi_2,\psi_1\circ \psi_2).$$ Therefore the automorphism group is $$S_m\times S_n$$ where $$S_m$$ and $$S_n$$ are permutation groups.