==== מכפלה קרטזית של גרפים ====
* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>\Big\{\Big((v,u_1,v),(u_2,v,u_2)\Big):</math> כאשר <math>v\ in V(G)\forall \{F_1and\ (u_1,F_2u_2)\}=in E(H)</math> או <math>\{GBig((v_1,Hu),(v_2,u)\}:\ vBig)</math> כאשר <math>u\in V(F_1H)\ \and\ (u_1v_1,u_2v_2)\in E(F_2G)\Big\}</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>.
* גרף הוא 2־צביע אם״ם הוא דו־צדדי.
* '''בעיית 4 הצבעים:''' לכל גרף מישורי סופי פשוט <math>G</math> הוא 4־צביע.
* <math>f_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\beginprod_{casesi=0}\frac^{x!n-1}{(x-ni)!},&x\ge n\\0,&\text{else}\end{cases}\ \and\ f_{P_n}(x)=x(x-1)^{n-1}</math>.
* <math>\forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x)</math>.
* <math>f_G</math> פולינום מתוקן ודרגתו <math>|V(G)|</math>.
* מספר ההילוכים מ־<math>v_i</math> ל־<math>v_j</math> מאורך <math>t</math> הוא <math>(A_G^t)_{i,j}</math>.
* מספר ההילוכים הסגורים מאורך <math>t</math> ב־<math>G</math> הוא <math>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).
* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spekspec}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H)</math>.* אם <math>G</math> גרף <math>d</math>־רגולרי אז <math>d\in\operatorname{spec}(G)</math> וו״ע מתאימים הם <math>v_A=(I_A(iv_i))_{i=1}^{|V(G)|}n</math> לכל רכיב קשירות <math>A\subseteq V(G)=\{v_i\}_{i=1}^n</math>.
* יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</math> ע״ע מאותו ריבוי.
* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.