הצגת המקור של תקציר תורת הגרפים, סמסטר א תשע״ג

בתקציר זה, אלא אם צוין אחרת, נסמן <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>(v,v)</math> כאשר <math>v\in V</math>.
* '''גרף פשוט''' הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־<math>E</math>).
* '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
** '''אי־הכוונה''' של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
** '''הכוונה''' של גרף לא מכוון היא הפיכתו לגרף מכוון. תיתכן יותר מהכוונה אפשרית אחת.
*** '''הכוונה מעגלית''' היא הכוונה שבה יש מעגל מכוון.
* '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
* '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</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_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>.
** '''גרף ''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)=\bigcup_{i\ne j}V^i\times V^j</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>.

==== עצים ====
* '''יער''' הוא גרף פשוט ללא מעגלים.
* '''עץ''' הוא יער קשיר.
* '''עלה''' הוא קודקוד בעץ שדרגתו 1.
* '''עץ פורש''' הוא תת־גרף פורש קשיר ללא מעגלים.

=== הילוכים ===
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <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>K(G)</math>.
* '''גרף קשיר''' הוא גרף שבו יש רכיב קשירות אחד.
* '''מסלול אוילר''' בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
* '''אוילריאן''' הוא גרף בו קיים מסלול אוילר סגור.
* '''סמי־אוילריאן''' הוא גרף בו קיים מסלול אוילר.
* '''מסילה המילטוניאנית''' בגרף היא מסילה המכילה את כל קודקודיו.
* '''מעגל המילטוניאני''' הוא מסילה המילטוניאנית סגורה.
* '''המילטוניאן''' הוא גרף בו קיים מעגל המילטוניאני.
* '''הילוך אקראי:''' יהי <math>G</math> גרף לא מכוון וסופי. במצב ההתחלתי <math>p_0</math> נמצאים על הקודקוד <math>v_0\in V(G)</math> בהסתברות 1, ובכל צעד פונים לשכן של הקודקוד הנוכחי כאשר לכל שכן הסתברות שווה. ההילוך שנוצר מקודקודים אלו נקרא הילוך אקראי.
* '''הסתברות החזרה''' בזמן <math>t</math> היא ההסתברות שלאחר <math>t</math> צעדים נהיה על הקודקוד בו התחלנו, ומסומנת <math>P_G(v_0,t)</math> כאשר <math>v_0</math> הקודקוד ההתחלתי.
* '''הסתברות החזרה הממוצעת''' בזמן <math>t</math> היא <math>P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t)</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>e=(u,v)</math> בגרף <math>G</math> היא <math>G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big)</math>.
* '''חלוקה''' של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.

==== כיווץ ====
* '''כיווץ''' של גרף <math>G</math> בצלע <math>e=(u,v)</math> הוא <math>G/e:=G\setminus\{u,v\}\cup\Big(\{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((v,u_1),(v,u_2)\Big)</math> כאשר <math>v\in V(G)\ \and\ (u_1,u_2)\in E(H)</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>\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> לאחר שהוציאו ממנו את התמונה של השיכון.
* '''גרף חוץ־מישורי''' הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.

=== גופים אפלטוניים ===
<gallery widths="75" hights="75" perrow="5" style="float:left;">
תמונה:Tetrahedron.jpg|טטרהדרון
תמונה:Hexahedron.jpg|הקסהדרון
תמונה:Octahedron.jpg|אוקטהדרון
תמונה:Dodecahedron.jpg|דודקהדרון
תמונה:Icosahedron.jpg|איקוסהדרון
</gallery>
* '''גוף אפלטוני''' הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים. הגופים האפלטונים הם הטטרהדרון (<math>K_4</math>), ההקסהדרון (קובייה, <math>K_2^{\times3}</math>), האוקטהדרון (<math>K_{2,4}</math>), הדודקהדרון והאיקוסהדרון.
* '''פאון דואלי''' של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.

=== צביעה ===
* '''''k''־צביעת קודקודים''' או '''''k''־צביעה''' בגרף <math>G</math> ללא לולאות היא פונקציה <math>f:V(G)\to[k]</math>.
* '''''k''־צביעה כשרה''' היא <math>k</math>־צביעה <math>f</math> שבה לכל צלע <math>(u,v)</math> מתקיים <math>f(u)\ne f(v)</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>V^1</math> ל־<math>V^2</math> בגרף <math>G</math> דו־צדדי ש־<math>V^1,V^2</math> הם צדדיו הינו התאמה חח״ע (לאו דווקא על) <math>f:V^1\to V^2</math> כך ש־<math>\forall u\in V^1:\ (u,f(u))\in E(G)</math>.

=== אי־תלות ===
* '''קבוצה בלתי־תלויה של צלעות''' בגרף <math>G</math> היא תת־קבוצה של <math>E(G)</math> שבה אין שתי צלעות בעלות קודקוד משותף.
* '''קבוצה בלתי־תלויה של קודקודים''' בגרף <math>G</math> היא תת־קבוצה של <math>V(G)</math> שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
* <math>\alpha(G)</math> הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־<math>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>n^{n-2}</math> עצים מסומנים מסדר <math>n</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>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=\prod_{i=0}^{n-1}(x-i)\ \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>.
* אם <math>r\mid n</math> אז <math>T(n,r)</math> הוא <math>\left(n-\frac nr\right)</math>־רגולרי ו־<math>\operatorname{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right)</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>\operatorname{tr}(A_G)</math> היא מספר הלולאות ב־<math>G</math>.
* יהי <math>G</math> פשוט ולא מכוון. אזי <math>\operatorname{tr}\!\left(A_G^2\right)=2|E(G)|</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>t</math> ב־<math>G</math> הוא <math>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).
* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spec}(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(v_i))_{i=1}^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> ע״ע מאותו ריבוי.
* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.
* הלפלסיאן של גרף לא מכוון הוא מטריצה סימטרית.
* הלפלסיאן אינו מטריצה הפיכה.
* אם <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>.