Graph G isomorphic to $K_{m,n}$

689 Views Asked by At

Theorem: Any complete bipartite graph G with a bipartition into two set of m and n vertices is isomorphic to $K_{m,n}$.

Proof:

Let $G={V(G),E(G)}$ be a complete graph. By definition of a complete graph, $\forall v_{1}, v_{2} \in V(G): v_{1}, v_{2}$ are joined by some edge $e_{1,2} \in E(G)$. Equivalently, no isolated vertex exists.

By definition of a bipartite graph G:

$\forall v_{1} \in X$ and $v_{2} \in Y: v_{1}$ and $v_{2}$ are joined by some edge $e \in E(G)$ and $\parallel X\parallel =m$ and $\parallel Y \parallel =n$ Denoting this graph by $K_{m,n}$, this is $G=K_{m,n}$.

I would like to continue with the proof but I'm confused by the claim - the wording seems give me a poor impression of what the author intends to convey. It seem that the theorem is really just claiming that the graph G is isomorphic to itself.

Can somebody clarify?

Edit: The use of the word "complete" here does not seem to be used in the strict sense of the definition of complete in graph theory.

1

There are 1 best solutions below

0
On

Let $A,B$ be a bipartition of $G$ with $|A|=m$ and $|B|=n$.

Let $C,D$ be a bipartition of $K_{m,n}$, with $|C|=m$, and $|D|=n$.

Let $h:A\to C$ and $k:B\to D$ be arbitrary bijective maps.

Let $f:G\to K_{m,n}$ be defined by $$ f(v) = \begin{cases} h(v)&\text{if}\;v\in A\\[4pt] k(v)&\text{if}\;v\in B\\[4pt] \end{cases} $$ It's routine to verify that $f$ is an isomorphism.

The essential content of the result is that, for given positive integers $m,n$, there is a unique complete bipartite graph, up to isomorphism, with a bipartition of cardinalities $m,n$.