Απόδειξη της πρότασης: << Όμως τα παραπάνω αθροίσματα είναι περιττοί αριθμοί >> από την άσκηση 6.

Έστω τα u , v τα δύο άκρα της ακμής e και έστω ότι u V(G₁ ) , v V(G₂ ). Στο γράφημα G-{e} ο βαθμός των κορυφών u , v θα είναι μικρότερος κατά 1 από το βαθμό που είχαν αυτές οι κορυφές στο γράφημα G₁. Όσο αφορά στον βαθμό των υπολοίπων κορυφών , αυτός παραμένει αμετάβλητος (δηλαδή οι υπόλοιπες κορυφές εξακολουθούν να έχουν άρτιο βαθμό στο G-{e} ).
Επομένως τα αθροίσματα είναι περιττοί αριθμοί.

Προηγούμενο

Ευρετήριο