Grafy

1. W ksi_{}estwie hofmańskim jest n miast w tym jedna stolica, niektóre z nich poł _{}aczone s _{}a jednokierunkowymi drogami. Wiadomo, że z każdego miasta wychodzi tyle samo dróg co wchodzi oraz że ze stolicy można dojechać do każdego miasta. Pokazać, że w każdego miasta można dojechać do stolicy.

2. W grupie n 3 osób każda ma parzyst _{}a (być może zerow _{}a) liczb_{}e znajomych. Pokazać, że istniej _{}a trzy osoby maj _{}ace tak _{}a sam _{}a liczb_{}e znajomych.

3. W turnieju tenisowym brało udział n graczy. Każdy rozegrał z każdym innym jeden mecz przy czym w tenisie nie ma remisów. Udowodnić, że istnieje taki gracz A, który pokonał każdego innego gracza B bezpośrednio lub pośrednio, tzn. A wygrał z B, lub A pokonał pewnego przeciwnika C, który wygrał z B.

4. W sali jest n chłopców i l n dziewcz _{}at. Wiadomo, że każda grupa k chłopców, gdzie 1 k n, zna przynajmniej k dziewcz _{}at. Pokazać, że każdemu chłopcu można przyporz _{}adkować dziewczynk_{}e do tańca tak, by wszyscy chłopcy znali swoje partnerki.

5. Pokazać, że graf jest dwudzielny wtedy i tylko wtedy, gdy wszystkie jego cykle s _{}a parzystej długości.

6. Na przyj_{}eciu spotkało sie n osób (n 5). Wiadomo, że wsród dowolnych trzech osób pewne dwie znaj _{}a si_{}e. Dowieść, że spośród uczestników przyj_{}ecia można wybrać nie mniej niż n/2 osób i posadzić przy okr _{}agłym stole tak, aby każdy siedział mi_{}edzy dwoma swoimi znajomymi.