Απόδειξη της πρότασης: <<Αυτές οι δ(G)-1 κορυφές ανήκουν στο Ρ>> από την άσκηση 2.

Έστω ότι υπάρχει κορυφή ν γειτονική προς την u₁, η οποία δεν ανήκει στο Ρ. Όμως σ'αυτή την περίπτωση το μονοπάτι νu₁u₂u₃ . . . u_m-1u_m έχει μεγαλύτερο μήκος από το Ρ-ΑΤΟΠΟ διότι υποθέσαμε ότι το Ρ είναι μέγιστου μήκους.

Προηγούμενο

Ευρετήριο