Věta

Počet koster úplného bipartitního grafu $K_{m,n}$ je $n^{m-1} m^{n-1}$.

Lemma

Mějme kostru T grafu $K_{m,n}, m \leq n$, s vrcholy rozdělenými na množiny $M=\{a_1,\dots,a_m\}$ a $N=\{b_1,\dots,b_n\}$, kde množiny $M,N$ jsou barvy přirozeného obarvení úplného bipartitního grafu. Pak pro nějaké k, $1 \leq k \leq n, deg(b_k)=1$.

Důkaz lemma

Mějme A,B součty stupňů vrcholů $a_i,b_j$ resp uvnitř T. Zřejmě $A=B$ a $(A+B)/2=m+n-1$, protože je to strom. Takže $$B = \frac{A+B}{2}=m+n-1,$$ a kdyby $deg(b_j)$ platilo pro všechny j, pak $$B \geq m+n > m+n-1,$$ což je spor.

$\square$

Důkaz věty

Mějme $m \leq n$ a partity $K_{m,n}$, $M=\{a_1,\dots,a_m\}$ a $N=\{b_1,\dots,b_n\}$. Dokážeme, že řada ve tvaru dělky $m+n-2$ ve tvaru $$a_{i_1},a_{i_2},\dots,a_{i_{n-m+1}},b_{j_1},a_{i_{n-m+2}},b_{j_2},\dots,a_{i_{n-1}},b_{j_{m-1}},$$ kde prvky a ani prvky b nemusí být nutně různé, je ekvivalentní stromu na $K_{m,n}$. Pozorujeme, že tato sekvence má přesně $m^{n-1} n^{m-1}$ různých variant.

Mějme kostru $T_0$ grafu $K_{m,n}$, pak sekvence $S_0$ je svázaná s $T_0$ následujícím způsobem. Pokud je $|M| \leq |N|$ ($|M| > |N|$), tak vezměme list s nejmenším ID z partity N (M resp.), který z lemma existuje, zapišme do řady $S_0$ jeho rodiče a odmažme ho z $T_0$, čímž vznikne strom $T_1$. Tento proces opakujeme dokud se nedostaneme k poslední hraně.

Je jasné, že zápis vybraného stromu je jednoznačný (popsali jsme algo.), ale je vybraný zápis zápisem k pouze jednomu stromu? idk…

Tento zápis je tzv. Prüferův kód, a 1 k 1 koresponduje se stromem.

$\square$

Zdroj