Писмени испит из предмета Дискретна математика

Испитати да ли следећи бипартитивни графови имају савршено упаривање. Уколико савршено упаривање не постоји, наћи максимално упаривање.

Одредити хроматски број и хроматски индекс следећих графова:

Испитати да ли су следећи графови планарни:

1. Ако је \(G\) повезан граф са \(n\) чворова показати да \(G\) садржи подграф \(T\) који је стабло и има \(n\) чворова
2. Доказати да повезан граф са \(n\) чворова и \(n\) грана има циклус.
3. Нека је \(G\) повезан граф са \(n \ge 4\) чворова и \(m\) грана. Ако је \(m\ge 2n-2\) показати да граф \(G\) има два циклуса исте дужине.

Нека је граф \(G\) 2-повезан и \(v\in V(G)\) произвољан чвор. Доказати да постоји чвор \(u\in V(G)\) такав да је \(G\setminus\{u,v\}\) повезан.