Matematyka.pl

Potrzebuję dowodu Twierdzenia Gallai dla grafów. Czyli: Dla dowolnego Grafu \(\displaystyle{ G=(V,E)}\) bez wierzchołków izolowanych mamy \(\displaystyle{ \alpha(G) + \tau(G) = |V|= \nu(G) +\rho(G)}\).

\(\displaystyle{ \nu(G)+\rho(G) = |V|}\)

Weźmy dowolne skojarzenie \(\displaystyle{ M}\) realizujące \(\displaystyle{ \nu(G)}\), w celu otrzymania pokrycia krawędziowego dołóżmy do niego po jednej krawędzi sąsiedniej z każdym wierzchołkiem \(\displaystyle{ V-V(M)}\) (nie ma wierzchołków izolowanych). Skonstruowane pokrycie jest wielkości \(\displaystyle{ |M|+(|V|-2|M|) = |V|-|M| \geq \rho(G)}\), zatem \(\displaystyle{ |V| \geq \nu(G)+\rho(G)}\).

Weźmy dowolne pokrycie krawędziowe \(\displaystyle{ F}\) realizujące \(\displaystyle{ \rho(G)}\), jest to las gwiazd, gdyż z dowolnego cyklu lub dowonej ścieżki długości co najmniej \(\displaystyle{ 3}\) moglibyśmy usunąć krawędź. W celu otrzymania skojarzenia, z każdej gwiazdy weźmy dowolnie wybraną krawędź, jest to równoważne usunięciu \(\displaystyle{ \text{deg}_F(v)-1}\) krawędzi w \(\displaystyle{ |F|}\) , dla każdego \(\displaystyle{ v \in V}\), zatem otrzymujemy skojarzenie wielkości \(\displaystyle{ |F|-\sum_{v \in V} (\text{deg}_F(v)-1) = |F|-(2|F|-|V|) = |V|-|F| \leq \nu(G)}\), zatem \(\displaystyle{ |V| \leq \nu(G)+\rho(G)}\).

\(\displaystyle{ \alpha(G)+\tau(G) = |V|}\)

Dla dowodu zauważ, że \(\displaystyle{ I}\) jest zbiorem niezależnym wtw \(\displaystyle{ V-I}\) jest pokryciem wierzchołkowym.