Άσκηση 1
Έστω G απλό γράφημα και k θετικός ακέραιος. Εάν δ(G) > k, να αποδειχθεί ότι το G περιέχει μονοπάτι μήκους k.
Απόδειξη:
Έστω Ρ μονοπάτι μεγίστου μήκους στο G και έστω ότι Ρ=u₁u₂u₃ . . . u_m-1u_m. Επειδή d_G(u₁)>δ(G)>k και επειδή το G είναι απλό,η κορυφή u₁, εκτός από την u₂, είναι γειτονική με τουλάχιστον άλλες k-1 κορυφές,

Αυτές οι k-1 κορυφές ανήκουν στο Ρ (γιατί;)

Άρα το Ρ περιέχει τουλάχιστον k-1 κορυφές εκτός από τις u₁, u₂ . Επομένως το Ρ περιέχει τουλάχιστον k+1 κορυφές, δηλαδή έχει μήκος τουλάχιστον k.

---

Άσκηση 2
Έστω G απλό γράφημα και k με δ(G) > 2. Nα αποδειχθεί ότι το G περιέχει κύκλο μήκους τουλάχιστον δ(G)+1.
Απόδειξη:
Έστω Ρ μονοπάτι μέγιστου μήκους στο G και έστω ότι Ρ=u₁u₂u₃ . . . u_m-1u_m. Επειδή d_G(u₁) > δ(G) > 2 και επειδή το G είναι απλό, η κορυφή u₁ εκτός από την u₂, είναι γειτονική με τουλάχιστον άλλες δ(G)-1 >0 κορυφές

Αυτές οι δ(G)-1 κορυφές ανήκουν στο Ρ (γιατί;)

Έστω u_j , η τελευταία κορυφή του Ρ, η οποία είναι γειτονική προς την u₁ (καθώς πηγαίνουμε από την u₁ στην u_m ).Τότε στο μονοπάτι Ρ και μεταξύ των κορυφών u₁ και u_j υπάρχουν δ(G)-1 κορυφές γειτονικές προς την u₁. Θεωρούμε τον κύκλο C=u₁u₂u₃ . . .u_ju₁. Ο C θα περιέχει εκτός των κορυφών u₁ , u_j και τουλάχιστον άλλες δ(G)-1 κορυφές. Άρα ο c θα έχει μήκος τουλάχιστον δ(G)+1.

---

Άσκηση 3
Έστω G k-κανονικό διμερές γράφημα με διαμερισμό (Χ,Y ). Να αποδειχθεί ότι |Χ|=|Υ|.
Απόδειξη:
Επειδή το G είναι διμερές, κάθε ακμή έχει ένα άκρο στο Χ και το άλλο άκρο στο Y. Άρα ο αριθμός των ακμών που έχουν άκρο στο Χ, ισούται με τον αριθμό των ακμών που έχουν άκρο στο Υ.Όμως το G είναι k-κανονικό, επομένως ο αριθμός των ακμών που έχουν άκρο στο Χ είναι k|Χ| ενώ ο αριθμός των ακμών που έχουν άκρο στο Y είναι k|Y|.
Άρα είναι k|Χ|=k|Y|,
οπότε |Χ|=|Y|.

---

Άσκηση 4
Άνοιγμα ενός γραφήματος ονομάζουμε το ελάχιστο μήκος κύκλου σ'αυτό το γράφημα. Εάν G k-κανονικό γράφημα με άνοιγμα 4, να αποδειχθεί ότι |V(G)|>2k.
Απόδειξη:
Έστω u τυχαία κορυφή του G . Επειδή το G είναι k-κανονικό, η u θα είναι γειτονική με ακριβώς k κορυφές.
Έστω S το σύνολο των γειτονικών κορυφών προς την u και έστω ότι S={u₁ , u₂ , . . . ,u_k}. Η κορυφή u₁ εκτός από την u θα είναι γειτονική με άλλες k-1 κορυφές. Έστω S' το σύνολο αυτών των k-1 κορυφών και έστω ότι S'={u'₁ , u'₂ , . . . ,u'_k-1}

Έχουμε ότι (γιατί;)

Θα έχουμε δηλαδή την παρακάτω εικόνα: Άρα |V(G)| >1+|S|+|S'|=1+k+(k-1)=2k.

---

Άσκηση 5
Έστω G απλό γράφημα με . Nα αποδειχθεί ότι το G είναι συνεκτικό γράφημα .
Απόδειξη:
Έστω ότι το G δεν είναι συνεκτικό γράφημα και έστω G₁ , G₂ , . . . , G_k οι συνιστώσες του. Εάν G_j συνιστώσα του G με τον μικρότερο αριθμό κορυφών, έχουμε ότι: Τώρα εάν u τυχαία κορυφή της G_j , διότι αυτή μπορεί να είναι γειτονική το πολύ με όλες τις υπόλοιπες κορυφές της συνιστώσας G_j, στην οποία ανήκει.Επομένως ΌμωςΆρα

---

Άσκηση 6
Έστω G συνεκτικό γράφημα στο οποίο όλες οι κορυφές έχουν άρτιο βαθμό. Να αποδειχθεί ότι για κάθε ακμή e του G, το γράφημα G-{e} είναι επίσης συνεκτικό.
Απόδειξη:
Έστω ότι υπάρχει ακμή e του G ώστε το G-{e} να είναι μη-συνεκτικό γράφημα.
Έστω επίσης G₁ , G₂ οι δύο συνιστώσες του G-{e}.
Από το γνωστό Θεώρημα, θα έχουμε ότι: που σημαίνει ότι τα παραπάνω αθροίσματα είναι άρτιοι αριθμοί.

Όμως τα παραπάνω αθροίσματα είναι περιττοί αριθμοί (γιατί;)

---

Άσκηση 7
Έστω G απλό γράφημα και έστω V(G)={ u₁ , u₂ , . . . , u_v }.
Εάν Α(G) είναι ο πίνακας γειτνίασης του G,να αποδειχθεί ότι το στοιχείο που βρίσκεται στην θέση ( m , s ) του πίνακα (Α(G))ⁿ αντιπροσωπεύει τον αριθμό των διαφορετικών ( u_m , u_s ) - περιπάτων μήκους n.
Απόδειξη:
Θα το αποδείξουμε με επαγωγή ως προς n

Εάν n=1, προφανώς η παραπάνω πρόταση ισχύει (γιατί;)

Έστω ότι ισχύει η παραπάνω πρόταση για n=k. Αυτό σημαίνει ότι το στοιχείο που βρίσκεται στην θέση ( m , s ) του πίνακα (Α(G))^k αντιπροσωπεύει τον αριθμό των διαφορετικών ( u_m , u_s ) - περιπάτων μήκους k.
Στην συνέχεια θεωρούμε τον πίνακα (Α(G))^k+1. Προφανώς (Α(G))^k+1=(Α(G))^{k .}Α(G).
Εάν (Α(G))ⁿ=[α_ij⁽ⁿ⁾] όπου i , j = 1 , 2 , . . . ,v τότε α_ms^(k+1)=α_m1^(k)α_1s+α_m2^(k)α_2s+ . . . +α_mv^(k)α_vs
Όμως

αmr(k)αrs= αριθμό των διαφορετικών ( um , us ) - περιπάτων μήκους k+1 που έχουν για προτελευταία τους κορυφή την ur (όπου r=1,2,...,v ) (γιατί;)

Άρα ο αριθμός α_ms^(k+1) εκφράζει τον αριθμό των διαφορετικών ( u_m , u_s ) - περιπάτων μήκους k+1.
Επομένως η πρόταση ισχύει και για n=k+1.

---

Προηγούμενο

Ευρετήριο