שינויים
בתקציר זה, אלא אם צוין אחרת, נסמן <math>[n]:=\{1,2,\dots,n\}</math>. <math>G,H</math> גרפים. <math>(\cdot,\cdot)</math> הוא זוג לא סדור (אלא אם מדובר בגרפים לא מכוונים) ומכפלה קרטזית <math>A\times B</math> של קבוצות היא קבוצת הזוגות הלא סדורים של איברי <math>A,B</math>.
== הגדרות ==
* '''גרף''' הוא זוג <math>G=(V,E)</math> כך ש־<math>V</math> קבוצת קודקודים (נקראים גם "צמתים") ו־<math>E</math> רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
* '''מידה''' של גרף היא מספר הצלעות – <math>|E|</math>. לעתים מסומנת <math>e(G)</math> או <math>m(G)</math>.
* '''דרגה''' של קודקוד <math>v\in V</math> היא מספר הצלעות העוברות בו. מסומנת <math>d(v)</math> או <math>d_G(v)</math>.
** '''הדרגה המקסימלית:''' <math>\Delta(G):=\max\{d_G(v):\ v\in V(G)\}</math>.
** '''הדרגה המינימלית:''' <math>\delta(G):=\min\{d_G(v):\ v\in V(G)\}</math>.
** '''דרגות החוץ והפנים''' של קודקוד בגרף מכוון הן <math>d_G^+(v):=|\{(v,u)\in E:\ u\in V\}|,\ d_G^-(v):=|\{(u,v)\in E:\ u\in V\}|</math> בהתאמה, כלומר מספר הצלעות היוצאות ומספר הצלעות הנכנסות לקודקוד בהתאמה.
* '''איחוד''' של גרפים פשוטים <math>G,H</math> הוא <math>G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)</math>. באותו אופן מוגדר איחוד זר.
* '''קבוצת השכנים''' של קודקוד <math>v</math> בגרף <math>G</math> היא <math>N_G(v):=\{u:\ (v,u)\in E(G)\}</math>. אם <math>A\subseteq V(G)</math> אז <math>N_G(A):=\bigcup_{v\in A}N_G(v)=\{u:\ \exists v\in A:\ (u,v)\in E(G)\}</math>.
=== סוגים סוגי גרפים נפוצים ===* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.-** '''קליקה''' בגרף היא תת־גרף מלא.-** '''מספר הקליקה''' של גרף <math>G</math> מסומן <math>\omega(G)</math> ושווה לסדר המקסימלי של קליקה ב־<math>G</math>.* '''מסילה''' מסדר <math>n</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>n>2C_n</math> (<math>C_nn\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>.** אם <math>\delta(G)\ge 2</math> אז יש ב־<math>G</math> מעגל.-** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.*** <math>g(G)\le2</math> אם״ם הגרף לא פשוט.
* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** '''גרף {{ltr|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=AV^1\uplus BV^2</math> כך שאם ש־<math>(u,v)\in E(G)</math> אז <math>u\in Asubseteq V^1\ \and\ v\in B</math> או <math>v\in A\ \and\ u\in Btimes V^2</math>.** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus UV^2</math> (כאשר <math>\left|V^1\right|=n,\left|U^2\right|=m</math>) וצלעותיו <math>V^1\{(v,u):\ v\in times V\ \and\ u\in U\}^2</math>.** '''גרף ''r''־צדדי''' הוא גרף <math>G</math> בו ישר יש חלוקה <math>V(G)=\biguplus_{i=1}^r V^i</math> ל־<math>r</math> תתי־קבוצות כך שלכל <math>i</math>, הקודקודים ב־<math>V^i</math> אינם שכנים, כלומר <math>E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j</math>.** '''גרף ''r''־צדדי מלא''' הוא גרף <math>r</math>־צדדי <math>G</math> בו <math>E(G)=\forall bigcup_{i\ne j:\ \forall u\in }V^i\ \and\ v\in times V^j:\ (u,v)\in E(G)</math>, כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.
** '''גרף ''r''־צדדי סימטרי''' הוא גרף <math>r</math>־צדדי בו <math>\forall i\in[r]:\ \left|V^i\right|\in\left\{\left\lfloor\frac{|V(G)|}r\right\rfloor,\left\lceil\frac{|V(G)|}r\right\rceil\right\}</math>.
** '''גרף טורן''' <math>T(n,r)</math> הוא הגרף ה־<math>r</math>־צדדי סימטרי מלאמסדר <math>n</math>.* '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <math>\{v_i\}_{i=1}^n</math>. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם <math>\varphi</math> בינהם כך ש־<math>\forall i:\ \varphi(v_i)=v_i</math>.
==== עצים ====
* '''יער''' הוא גרף פשוט ללא מעגלים.
=== הילוכים ===
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <math>v_0,v_1,\dots,v_n</math> כך ש־<math>\forall i:\ (v_i,v_{i+1})\in E</math>.
** אורך ההילוך הוא <math>n</math> – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
** ההילוך '''סגור''' אם <math>v_0=v_n</math>.
* '''המרחק בין שני קודקודים''' <math>u,v</math> הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן <math>\operatorname{dist}_G(u,v)</math>.
* '''הקוטר''' של גרף הוא <math>\operatorname{diameter}(G)=\max\{\operatorname{dist}_G(u,v):\ u,v\in V(G)\}</math>.
* '''מסלול''' הוא הילוך שבו אין צלעות חוזרות.
* '''מסילה''' היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
* '''רכיב קשירות''' בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות <math>\rightarrow</math> המקיים <math>u\rightarrow v</math> אם״ם יש מסילה בין <math>u,v</math>.
* '''מסלול אוילר''' בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
* '''מסילה המילטוניאנית''' בגרף היא מסילה המכילה את כל קודקודיו.
=== תתי איזומורפיזם ===* '''איזומורפיזם''' בין מגרף <math>G</math> לגרף <math>H</math> הוא פונקציה <math>\varphi:V(G)\to V(H)</math> חח״ע ועל ששומרת צלעות, כלומר <math>(u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H)</math> לכל <math>u,v\in V(G)</math>. אם קיים איזומורפיזם בין <math>G,H</math> אז נאמר שהם איזומורפיים ונסמן <math>G\cong H</math> (זה יחס שקילות).* '''גרף טרנזיטיבי קודקודים''' הוא גרף <math>G</math> בו לכל <math>u,v\in V(G)</math> קיים אוטומורפיזם <math>\varphi:V(G)\to V(G)</math> כך ש־<math>\varphi(u)=v</math>. === גרפים הנוצרים מגרפים אחרים ======= תת־גרף ====
* '''השמטת צלע''' <math>e\in E</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{e\}:=(V,E\setminus\{e\})</math>.
* '''השמטת קודקוד''' <math>v\in V</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\})</math>.
* '''תת־גרף''' הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
=== איזומורפיזם = חלוקה ====* '''איזומורפיזםחלוקה אלמנטרית''' בין מגרף <math>G</math> לגרף <math>H</math> הוא פונקציה <math>\varphi:V(G)\to V(H)</math> חח״ע ועל ששומרת צלעות, כלומר של צלע <math>e=(u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H)</math> לכל בגרף <math>u,v\in V(G)</math>. אם קיים איזומורפיזם בין <math>G,H</math> אז נאמר שהם איזומורפיים ונסמן היא <math>G\cong H</math> (זה יחס שקילות).* אם <math>Gsetminus\cong H</math> אז הפרמטרים הבאים שווים:** סדר: <math>|V{e\}\cup\Big(G)|=|V(H)|</math>.** מידה: <math>|E(G)|=|E(H)|</math>.** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).** קוטר: <math>\operatorname{diametere\}(G)=,\operatorname{diameter}(Hu,e),(v,e)</math>.* '''גרף מסומן''' הוא גרף שקודקודיו סומנו ע״י <math>\{v_i\}_{i=1}^n</math>. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם <math>\varphi</math> בינהם כך ש־<math>\forall i:\ \varphi(v_iBig)=v_i</math>.** '''משפט קיילי:חלוקה''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.
==== כיווץ ====* '''גרף טרנזיטיבי קודקודיםכיווץ''' הוא של גרף <math>G</math> בו לכל בצלע <math>e=(u,v\in V(G)</math> קיים אוטומורפיזם הוא <math>\varphiG/e:V(=G)\to Vsetminus\{u,v\}\cup\Big(G)</math> כך ש־<math>\varphi{e\},\{e\}\times(N_G(u)=\cup N_G(v))\Big)</math>.* '''מינור''' של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות.* '''תכונה מונוטונית''' של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה.
==== גרף משלים ====
* '''הגרף המשלים''' של גרף <math>G=(V,E)</math> הוא <math>\overline G:=(V,V^2\setminus E)</math>.
==== גרף הקו ====
* '''גרף הקו''' של גרף פשוט <math>G</math> מסומן <math>L(G)</math> ומוגדר כגרף שקודקודיו הם <math>E(G)</math> וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־<math>G</math>, כלומר <math>E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\}</math>.
==== מכפלה קרטזית של גרפים ====
* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> וצלעותיו <math>\Big\{\Big((u_1,v),(u_2,v)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ v\in V(F_1)\ \and\ (u_1,u_2)\in E(F_2)\Big\}</math>.
* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>. היא איזומורפית ל־<math>B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\})</math> ול־<math>H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\})</math>.
=== שיכון ===
* '''שיכון''' של גרף <math>G</math> ב־<math>\mathbb R^n</math> הוא העתקה חח״ע <math>\varphi:V(G)\to\mathbb R^n</math>. כל צלע <math>(u,v)\in E(G)</math> מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־<math>\varphi(u)</math> ל־<math>\varphi(v)</math>.
* '''שיכון נאות''' הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־<math>\mathbb R^n</math> חותכות זו את זו רק בתמונות של קודקודי הגרף.
* '''גרף מישורי''' הוא גרף שניתן לשיכון נאות ב־<math>\mathbb R^2</math>.
* '''פאה''' של שיכון נאות ב־<math>\mathbb R^2</math> היא רכיב קשירות ב־<math>\mathbb R^2</math> לאחר שהוציאו ממנו את התמונה של השיכון.
* '''גרף חוץ־מישורי''' הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
=== גופים אפלטוניים ===
תמונה:Icosahedron.jpg|איקוסהדרון
</gallery>
* '''גוף אפלטוני''' הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים.* הגופים האפלטונים הם הטטרהדרון (<math>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.* הגרף של כל גוף אפלטוני הוא מישורי.
* '''פאון דואלי''' של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.
* '''מספר הצביעה''' או '''המספר הכרומטי''' של גרף <math>G</math> מסומן כ־<math>\chi(G)</math> ומוגדר כ־<math>k</math> המינימלי עבורו קיימת <math>k</math>־צביעה כשרה.
* '''גרף ''k''־צביע''' הוא גרף שקיימת לו <math>k</math>־צביעה כשרה, כלומר <math>\chi\le k</math>.
* '''פולינום הצביעה''' בגרף פשוט וסופי מסומן <math>f_G</math>. לכל <math>x</math> טבעי <math>f_G(x)</math> מוגדר כמספר ה־<math>x</math>־צביעות הכשרות. לשאר ה־<math>x</math>־ים <math>f_G(x)</math> הוא ההשלמה של <math>f_G</math> לפולינום.
* '''''k''־צביעת צלעות''' בגרף <math>G</math> היא פונקציה <math>f:E(G)\to[k]</math>.
* '''''k''־צביעת צלעות כשרה''' היא <math>k</math>־צביעת צלעות בה אם לשתי צלעות יש קודקוד משותף אז הן צבועות בצבעים שונים.
* '''אינדקס הצביעה''' <math>i(G)</math> של גרף <math>G</math> הוא ה־<math>k</math> המינימלי עבורו קיימת <math>k</math>־צביעת צלעות כשרה.
=== שידוכים שידוך ===
* '''שידוך''' בגרף <math>G</math> הוא התאמה חח״ע ועל <math>f:A\to B</math> כאשר <math>A\uplus B\subseteq V(G)</math> ו־<math>\forall u\in A:\ (u,f(u))\in E(G)</math>.
* '''שידוך מושלם''' <math>f:A\to B</math> הוא שידוך בו <math>A\uplus B=V(G)</math>.
=== אי־תלות ===
=== בעיות קיצון ===
* '''בעיית טורן:''' בהנתן גרף <math>H</math> (או קבוצת גרפים <math>\mathbb H</math>) ומספר טבעי <math>n</math> יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר <math>n</math> שאין לו תת־גרף איזומורפי ל־<math>H</math> (או לאחד מהגרפים ב־<math>\mathbb H</math>). מספר זה מסומן כ־<math>\operatorname{ex}(n,H)</math> או <math>\operatorname{ex}(n,\mathbb H)</math> וגרף כזה נקרא ''גרף מרבי נמנע <math>H</math> (או <math>\mathbb H</math>)''.
* '''מספר רמזי''' <math>R(s,t)</math> הוא הסדר המינימלי כך שאם <math>G</math> גרף מסדר זה אז <math>K_s</math> תת־גרף של <math>G</math> או ש־<math>K_t</math> תת־גרף של <math>\overline 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>\sum_{v\in V}d_G(v)=2|E(G)|</math>.
* <math>\sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E(G)|</math>.
* אם <math>\delta(G)\ge 2</math> אז יש ב־<math>G</math> מעגל.
* <math>g(G)\le2</math> אם״ם הגרף לא פשוט.
* גרף הוא ריק אם״ם הוא 0־רגולרי.
* גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
* גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
* אם גרף סופי ופשוט הוא <math>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי.
* גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
* בכל עץ סופי מסדר גדול מ־1 יש עלה.
* גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
* גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
* לכל גרף קשיר וסופי קיים עץ פורש.
* מספר העצים הפורשים של גרף של <math>K_n</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>n\in\mathbb N</math> עם <math>k</math> רכיבי קשירות יש <math>n-k</math> צלעות.
* גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־<math>K_3</math>.
* כל מסילה היא מסלול.
* קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
* גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
* '''משפט אוילר:''' גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
* גרף <math>G</math> קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
* '''משפט דיראק:''' יהי <math>G</math> גרף פשוט מסדר <math>n</math>. אם <math>\delta(G)\ge\frac n2</math> אז <math>G</math> המילטוניאן.
* אם <math>G\cong H</math> אז הפרמטרים הבאים שווים:
** סדר: <math>|V(G)|=|V(H)|</math>.
** מידה: <math>|E(G)|=|E(H)|</math>.
** מספר רכיבי הקשירות: <math>K(G)=K(H)</math>.
** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
** קוטר: <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>.
* הקובייה ה־<math>n</math> מימדית <math>K_2^{\times n}</math> איזומורפית ל־<math>B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\})</math> ול־<math>H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\})</math>.
* לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־<math>\mathbb R^3</math> כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, <math>\forall i:\ \varphi(v_i)=(i,i^2,i^3)</math> כאשר <math>V=\{v_i\}_{i=1}^n</math>.
* '''משפט הפאון של אוילר:''' לכל גרף מישורי סופי קשיר מסדר <math>n</math> וממידה <math>m</math> מספר הפאות <math>f</math> לא תלוי בשיכון הנאות ומקיים <math>n-m+f=2</math>.
* יהי <math>G</math> גרף פשוט וקשיר מסדר <math>n\ge3</math>. אם <math>G</math> מישורי אז <math>|E(G)|\le3n-6</math>.
* יהי <math>G</math> פשוט וקשיר מסדר <math>n</math> ומותן <math>g<\infty</math>. אם <math>G</math> מישורי אז <math>|E(G)|\le g\frac{n-2}{g-2}</math>.
* לכל גרף מישורי פשוט סופי <math>G</math> מתקיים <math>\delta(G)\le5</math>.
* '''משפט קורטובסקי:''' גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של <math>K_5</math> או של <math>K_{3,3}</math>.
* גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־<math>K_4</math> או ל־<math>K_{2,3}</math>.
* '''השערת וגנר:''' כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של <math>G</math> אם״ם הוא אינו מקיים את התכונה.
* '''משפט רוברטסון–סימור:''' השערת וגנר נכונה.
* הגרף של כל גוף אפלטוני הוא מישורי.
* לכל גרף <math>G</math> פשוט <math>1\le\chi(G)\le|V(G)|</math>. <math>\chi(G)=1</math> אם״ם <math>G</math> גרף ריק ו־<math>\chi(G)=|V(G)|</math> אם״ם הוא גרף מלא.
* '''משפט ברוקס:''' לכל גרף <math>G</math> פשוט וסופי <math>\chi(G)\le\Delta(G)+1</math> ושוויון מתקיים אם״ם <math>\omega(G)=\Delta(G)+1</math> או אם <math>G</math> איחוד זר של מעגלים ומסילות ויש מעגל מסדר אי־זוגי.
* יהא <math>G</math> פשוט וסופי. <math>\chi(G)\le2</math> אם״ם אין ב־<math>G</math> מעגלים מאורך אי־זוגי.
* גרף הוא 2־צביע אם״ם הוא דו־צדדי.
* '''בעיית 4 הצבעים:''' לכל גרף מישורי סופי פשוט <math>G</math> הוא 4־צביע.
* <math>f_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\begin{cases}\frac{x!}{(x-n)!},&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>\chi(G)=\max\{x\in\mathbb N_0:\ f_G(x)=0\}+1</math>.
* '''משפט סטנלי:''' מספר ההכוונות הלא מעגליות של <math>G</math> הוא <math>(-1)^n f_G(-1)</math>.
* לכל גרף <math>G</math> סופי <math>\Delta(G)\le i(G)</math>. אם הוא לא ריק אז <math>i(G)\le2\Delta(G)-1</math>.
* אם <math>G</math> דו־צדדי ו־<math>d</math>־רגולרי אז <math>i(G)=d</math>.
* אם <math>f:A\to B</math> שידוך אז <math>\{(u,f(u)):\ u\in A\}</math> קבוצה בלתי־תלויה.
* '''משפט הול (Hall):''' לכל גרף דו־צדדי שצדדיו <math>V^1,V^2</math> קיים שידוך מלא מ־<math>V^1</math> ל־<math>V^2</math> אם״ם <math>\forall A\subseteq V^1:\ |N_G(A)|\ge|A|</math>.
* '''משפט טורן:''' הגרף המרבי נמנע <math>K_r</math> היחיד מסדר <math>n</math> הוא <math>T(n,r-1)</math>.
* '''למת לחיצות הידיים:''' עבור כל גרף פשוט מסדר 6 או ש־<math>G</math> מכיל משולש או ש־<math>\overline G</math> מכיל משולש. (למעשה, <math>R(3,3)=6</math>.)
* <math>R(1,t)=1\ \and\ R(2,t)=t\ \and\ R(s,t)=R(t,s)</math> ואם <math>t,s\ge3</math> אז <math>R(s,t)\le R(s-1,t)+R(s,t-1)</math>.
* <math>R(s,t)\le\binom{s+t-2}{s-1}</math>.
* אם <math>G</math> לא מכוון אז <math>A_G</math> סימטרית.
* לכל גרף סופי מתקיים <math>\sum_{i=1}^n a_{ij}=d_G^-(v_j)\ \and\ \sum_{j=1}^n a_{ij}=d_G^+(v_i)</math>.
* יהי <math>G</math> לא מכוון. אזי <math>|E(G)|=\sum_{i\le j}a_{ij}</math>.
* מספר ההילוכים מ־<math>v_i</math> ל־<math>v_j</math> מאורך <math>t</math> הוא <math>(A_G^t)_{i,j}</math>.
* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spek}(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(i))_{i=1}^{|V(G)|}</math> לכל רכיב קשירות <math>A\subseteq V(G)</math>.
* יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</math> ע״ע מאותו ריבוי.
* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.
* הלפלסיאן של גרף לא מכוון היא הוא מטריצה סימטרית.
* הלפלסיאן אינו מטריצה הפיכה.
* אם <math>G</math> לא מכוון סופי אז <math>\operatorname{rank}(L_G)=|V(G)|-K(G)</math>.
* בגרף טרנזיטיבי קודקודים <math>\forall v\in V(G):\ P_G(v,t)=P_G(t)</math>.
* יהא <math>G</math> לא מכוון, סופי ו־<math>d</math>־רגולרי מסדר <math>n</math>. אזי <math>\forall t\in\mathbb N_0:\ P_G(t)=\sum_{\lambda\in\operatorname{spec}(A_G)}\frac{\lambda^t}{d^tn}=\frac{\operatorname{tr}\!\left(A_G^t\right)}{d^tn}</math>.