Ταίριασμα ενός γραφήματος είναι ένα σύνολο ακμών οι οποίες δεν έχουν κανένα κοινό άκρο και λέγεται τέλειο εάν κάθε κορυφή του γραφήματος προσπίτει σε κάποια ακμή του ταιριάσματος. Σκοπός της διπλωματικής είναι η μελέτη αλγοριθμικών και δομικών ιδιοτήτων γραφημάτων με τέλεια ταιριάσματα. Συγκεκριμένα, εστιάζουμε στην ακόλουθη ερώτηση: Υποθέτοντας ότι το k είναι ένας θετικός ακέραιος και G είναι ένα γράφημα, είναι το G k-επεκτάσιμο; Δηλαδή, είναι αλήθες ότι για κάθε ταίριασμα M στο G πληθυκότητας k υπάρχει κάποιο τέλειο ταίριασμα που περιέχει όλες τις ακμές του M;
Υπάρχει άμεση συσχέτιση στον δομικό χαρακτηρισμό των k-επεκτάσιμων διμερών γραφημάτων G με τέλεια ταιριάσματα και στην ύπαρξη k ξένων μονοπατιών, που είναι ανάλογο του θεωρήματος του Menger. Υποθέτοντας ότι το ζεύγος (U, V ) είναι μία διαμέριση των κορυφών του G και M είναι ένα τέλειο ταίριασμα του, το G είναι k−επεκτάσιμο εάν και μόνον εάν υπάρχουν k εσωτερικώς διακεκριμένα M- εναλλασόμενα μονοπάτια μεταξύ κάθε κορυφής του U και κάθε κορυφής του V. Ισχυρότερα, αποδεικνύεται ότι είναι δυνατόν να βρεθούν αυτά τα k μονοπάτια για οποιοδήποτε άλλο ταίριασμα M0 του G χρησιμοποιώντας τα γνωστά k μονοπάτια του τέλειου ταιριάσματος M.
Από υπολογιστικής απόψεως, το Extendability πρόβλημα εστιάζει στο εάν ένα γράφημα G είναι k−επεκτάσιμο, όπου (G, k) είναι η είσοδος. Η επεκτασιμότητα ενός γραφήματος G, η οποία συμβολίζεται ext(G), ορίζεται ως η μέγιστη τιμή του k για το οποίο το G είναι k-επεκτάσιμο. Στην γενική περίπτωση, αυτό το πρόβλημα είναι coNP-πλήρες. Στην περίπτωση όπου το G είναι διμερές, υπάρχει πολυωνυμικός αλγόριθμος που υπολογίζει το ext(G). Συνεπώς, το προαναφερθέν πρόβλημα μπορεί να αποφασιστεί σε πολυωνυμικό χρόνο ως προς τον αριθμό των κορυφών και των ακμών του G.