Siema, czy mógłby sprawdzić ktoś mój dowód? Jak uzasadnić istnienie minimalnego podgrafu spójnego rozpinającego?
Każdy graf spójny ma drzewo rozpinające.
Dowód:
Weźmy minimalny podgraf spójny rozpinający. Przypuśćmy że ma cykl. Usunięcie dowolnej krawędzi z tego cyklu nie popsuje nam spójności, a w ten sposób otrzymamy mniejszy podgraf rozpinający sprzeczność.