משפט נילסן-שרייר – הבדלי גרסאות

כעת נסמן {A={a₁,...,a_n,a₁^-1,...,a_n^-1. לכל קודקוד v ולכל איבר מ-A, "ללכת על האיבר" פירושו יהיה: אם האיבר הוא a_i, לעבור לקודקוד u כך שיש קשת מ-v ל-u עם הסימן a_i, ואם האיבר a_i^-1, לעעבורלעבור לקודקוד u כך שיש קשת מ-u ל-v עם הסימן a_i, ואם האיבר a_i^-1. (מוגדר היטב כי ראינו שלכל יוצר וקודקוד יש קשת אחת נכנסת ואחת יוצאת מכל סימן) כמו כן למילה w נגדיר "ללכת על המילה" ללכת אחד אחד על איבריה. קל לראות באינדוקציה שאם נצא מהקודקוד Hx ונלך על המילה w נגיע לקודקוד Hxw. מכאן נובע מייד שהגרף קשיר כי כדי להגיע מהקודקוד Hx לקודקוד Hy אפשר ללכת על המילה x^-1y.