נוסחת קיילי – הבדלי גרסאות

הבנייה היא עבורבהנתן עץ עם <math>n</math> קודקודים הממוספרים מ-1 עד <math>n</math> נבנה ממנו מילה שאורכה <math>n-2</math>. בשלב הראשון נמצא את העלה שמספרו הוא הקטן ביותר, במקרה של האיור זהו העלה מספר 1. מספר הצומת שאליו מחובר העלה יהיה האות הראשונה בקוד פרופר, כך שבדוגמה האות הראשונה בקוד היא 4. עתה מוחקים את העלה, וחוזרים על התהליך: מחפשים את העלה הקטן ביותר, מוסיפים לקוד את המספר של הצומת אליו מחובר העלה ומוחקים את העלה. חוזרים על הפעולה הזאת עד שנשארים לבסוף עם גרף המכיל שני צמתים בלבד המחוברים בקשת. מכיוון שבגרף המקורי היו n צמתים, במהלך התהליך מחקנו <math>n-2</math> צמתים ולכן בסיום אנחנו מקבלים קודמילה המורכבשאורכה מ- n-2 אותיות.

הבנייה מראה התאמה של עץ למילת קוד בעל <math>n-2</math> אותיות. כעת נראה שיש גם התאמה מכל קודמילה שלבאורך n-2 אותיות מעל אלפבית בגודל n לעץ פורש בעל n קודקודים.

נשים לב שהדרגה של כל צומת בעץ שווה למספר הפעמים שהצומת מופיע בקוד פרופר ועוד אחד. מכאן על מנת לייצר עץ מתוך קודמילה נתוןנתונה, נתחיל בכך שנחשב באופן זה את הדרגה של כל צומת. עתה נבדוק מבין כל הצמתים בעלי דרגה 1, דהיינו אלה שכלל לא הופיעו במילה, מהו הצומת בעלבשמספרו הסידורי המספרהוא הקטן ביותר. האות הראשונה בקוד פרופר מציינת קשת בין צומת זה לבין המספר הראשון בקוד. באופן זה ממשיכים את התהליך עד אשר מייצרים את העץ המתאים לקוד.

מכאן שיש [[איזומורפיזםהתאמה (מתמטיקה)|איזומורפיזםחד חד ערכית]] בין עצים בעלי n קודקודים למילים המכילות n-2 אותיות מתוך n אותיות אפשריות. מספר המילים הללו הוא <math>\ n^{n-2}</math>, ומכאן נובעת נוסחת קיילי.