Witam, potrzebuje pomocy w zrobieniu zadań z grafów:
1) Pokazać, że jeśli \(\displaystyle{ T}\) jest drzewem z co najmniej jednym wierzchołkiem o stopniu 2, to dopełnienie \(\displaystyle{ T}\) nie jest grafem eulerowskim.
2) Dla danych grafów \(\displaystyle{ G}\) i \(\displaystyle{ H}\) niech graf \(\displaystyle{ G + H}\) oznacza graf taki, że \(\displaystyle{ V(G + H) = V(G) \cup V (H), E(G + H) = E(G) \cup E(H) \cup { uw:u \in V(G), w \in V(H)}}\)
Kołem \(\displaystyle{ W _{n+1}}\) nazywamy graf \(\displaystyle{ C _{n} + K _{1}}\). Ile wynosi spójność wierzchołkowa \(\displaystyle{ (n \ge 4)}\), a ile krawędziowa dla koła?? Ile wynosi jego indeks chromatyczny??
3) Dany jest jedenastoelementowy zbiór \(\displaystyle{ X}\). W oparciu o ten zbiór budujemy graf w następujący sposób: wierzchołkami grafu są dwuelementowe podziory zbioru X, zaś dwa wierzchołki są sąsiednie wtt, gdy odpowiadające im podzbiory mają niepuste przecięcie. Czy otrzymany w ten sposób graf jest planarny??