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 G–u–w posiada doskonałe skojarzenie.
Zadanie 4. Udowodnij, że jeżeli G jest elementarny to każda krawędź w G jest dozwolona.