Hej! Możecie mi pomóc z zadaniami?
1. W grafie prostym \(\displaystyle{ G = }\) dla każdej nie połączonej pary wierzchołków \(\displaystyle{ x}\) i \(\displaystyle{ y}\) zachodzi \(\displaystyle{ deg(x)+deg(y) qslant |V|-1}\). Pokazać, że graf \(\displaystyle{ G}\) jest półhamiltonowski.
2. W grafie spójnym \(\displaystyle{ G}\) \(\displaystyle{ 2k}\) wierzchołków ma stopień nieparzysty, a pozostałe wierzchołki są stopnia parzystego. Pokazać, że w grafie \(\displaystyle{ G}\) istnieje \(\displaystyle{ k}\) krawędziowo rozłącznych dróg prostych, które pokrywają wszystkie krawędzie \(\displaystyle{ G}\).
Dzięki.