* '''גרף ריק''' <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
* '''גרף מלא/שלם''' <math>K_n</math> הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
-** '''קליקה''' בגרף היא תת־גרף מלא.-** '''מספר הקליקה''' של גרף <math>G</math> מסומן <math>\omega(G)</math> ושווה לסדר המקסימלי של קליקה ב־<math>G</math>.
* '''מסילה''' <math>P_n</math> היא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}</math>.
* '''מעגל''' <math>C_n</math> (<math>n\ge3</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}\cup\{(v_n,v_1)\}</math>.
-** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.
* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** '''גרף {{ltr|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת דרגת החוץ של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=V^1\uplus V^2</math> כך ש־<math>E(G)\subseteq V^1\times V^2</math>.
** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus V^2</math> (כאשר <math>\left|V^1\right|=n,\left|V^2\right|=m</math>) וצלעותיו <math>V^1\times V^2</math>.
==== מכפלה קרטזית של גרפים ====
* '''המכפלה הקרטזית''' של הגרפים <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>G</math> (מכוון או לא) כך ש־<math>V=\{v_i\}_{i=1}^n</math> היא <math>A_G\in\mathbb N_0^{n\times n}</math> שבה <math>a_{ij}</math> הוא מספר הצלעות מ־<math>v_i</math> ל־<math>v_j</math>.
* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).
* '''מטריצת הדרגות''' של גרף <math>G</math> מסדר <math>n</math> שקודקודיו <math>V(G)=\{v_i\}_{i=1}^n</math> הוא היא המטריצה <math>D_G:=\Big(\delta_{ij}d_G(v_i)\Big)_{i,j=1}^n</math>.
* '''הלפלסיאן''' של <math>G</math> הוא <math>L_G:=D_G-A_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> ע״ע מאותו ריבוי.
* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.