==== מכפלה קרטזית של גרפים ====
* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>\Big\{\Big((u_1,v,u_1),(u_2,v,u_2)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ </math> כאשר <math>v\in V(F_1G)\ \and\ (u_1,u_2)\in E(F_2H)</math> או <math>\Big((v_1,u),(v_2,u)\}Big)</math> כאשר <math>u\in V(כשהצלעות זוגות לא סדורים של קודקודיםH)\ \and\ (v_1,v_2)\in E(G)</math>.
* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.
=== אי־תלות ===
* '''קבוצה בלתי־תלויה של צלעות''' בגרף <math>G</math> היא תת־קבוצה של <math>E(G)</math> שבה אין שתי צלעות בעלות קודקוד משותף.
* '''קבוצה בלתי תלויה בלתי־תלויה של קודקודים''' בגרף <math>G</math> היא תת־קבוצה של <math>V(G)</math> שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
* <math>\alpha(G)</math> הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־<math>G</math>.
* גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
* לכל גרף קשיר וסופי קיים עץ פורש.
* מספר העצים הפורשים של גרף של '''משפט קיילי:''' יש <math>K_nn^{n-2}</math> הוא עצים מסומנים מסדר <math>n^{n-2}</math>.
* '''משפט מטריצה–עץ/משפט עצים פורשים:''' כידוע, מינור <math>A[i,j]</math> של מטריצה <math>A</math> הוא המטריצה המתקבלת מהשמטת השורה ה־<math>i</math> והעמודה ה־<math>j</math>. נסמן <math>\hat A</math> כמינור המוחק את השורה והעמודה האחרונות. עתה יהי <math>G</math> גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־<math>\det\!\left(\hat L_G\right)</math>.
* '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
** קוטר: <math>\operatorname{diameter}(G)=\operatorname{diameter}(H)</math>.
* '''משפט קיילי:''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>.
* <math>G\cong H</math> אם״ם <math>\overline G\cong\overline H</math>.
* <math>L(P_n)\cong P_{n-1},L(C_n)\cong C_n</math>.