Zpět na stránku cvika

7. série domácích úkolů

Deadline je v pondělí 30. 11. 2020 v době začátku cvika.

Příklad 1. Pro která $n$ existuje graf na $n$ vrcholech takový, že on i jeho doplněk jsou bipartitní?

(2 body)

Příklad 2. Kolik existuje na $[n]$ různých (ale ne nutně neizomorfních):

1. Úplných bipartitních grafů (na rozdíl od příkladu ze cvičení bez ohledu na velikost partit)?
2. Kružnic?

(1.5 + 1.5 bodů)

Příklad 3. V grafu na 15 vrcholech má každý vrchol stupeň nejméně 7. Je tento graf už nutně souvislý?

(2 body)