Cwiczenia do wykladu 3

Niech G=(V,E) będzie grafem dwudzielnym o podziale wierzchołków na U i W. Krawędź e nazwiemy dozwoloną w G wtedy gdy istnieje skojarzenie doskonałe zawierające e. Natomiast graf G nazwiemy elementarnym wtedy gdy jego krawędzie dozwolone tworzą podgraf spójny.

Zadanie 1. Udowodnij, że jeżeli G jest elementarny to posiada dokładnie dwa minimalne pokrycia wierzchołkowe i są to U i W.

Zadanie 2. Udowodnij, że jeżeli G jest elementarny to gdy |U|=|W| i dla każdego niepustego właściwego podzbioru X zbioru U zachodzi |N(X)| >= |X|+1.

Zadanie 3. Udowodnij, że jeżeli G jest elementarny to G=K_2 bądź, |V|>=4 i dla każdego u w U oraz w w W graf Guw posiada doskonałe skojarzenie.

Zadanie 4. Udowodnij, że jeżeli G jest elementarny to każda krawędź w G jest dozwolona.