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

בתקציר זה, אלא אם צוין אחרת, נסמן [math]\displaystyle{ [n]:=\{1,2,\dots,n\} }[/math]. [math]\displaystyle{ G,H }[/math] גרפים. [math]\displaystyle{ (\cdot,\cdot) }[/math] הוא זוג לא סדור (אלא אם מדובר בגרפים לא מכוונים) ומכפלה קרטזית [math]\displaystyle{ A\times B }[/math] של קבוצות היא קבוצת הזוגות הלא סדורים של איברי [math]\displaystyle{ A,B }[/math].

הגדרות

• גרף הוא זוג [math]\displaystyle{ G=(V,E) }[/math] כך ש־[math]\displaystyle{ V }[/math] קבוצת קודקודים (נקראים גם "צמתים") ו־[math]\displaystyle{ E }[/math] רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
• לולאה היא צלע [math]\displaystyle{ (v,v) }[/math] כאשר [math]\displaystyle{ v\in V }[/math].
• גרף פשוט הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־[math]\displaystyle{ E }[/math]).
• גרף מכוון הוא גרף בו הצלעות הן זוגות סדורים.
  • אי־הכוונה של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
  • הכוונה של גרף לא מכוון היא הפיכתו לגרף מכוון. תיתכן יותר מהכוונה אפשרית אחת.
    • הכוונה מעגלית היא הכוונה שבה יש מעגל מכוון.
• גרף סופי הוא גרף בו [math]\displaystyle{ |V|,|E|\lt \infty }[/math].
• סדר של גרף הוא מספר הקודקודים בו, כלומר [math]\displaystyle{ |V| }[/math]. לעתים מסומן [math]\displaystyle{ n(G) }[/math].
• מידה של גרף היא מספר הצלעות – [math]\displaystyle{ |E| }[/math]. לעתים מסומנת [math]\displaystyle{ e(G) }[/math] או [math]\displaystyle{ m(G) }[/math].
• דרגה של קודקוד [math]\displaystyle{ v\in V }[/math] היא מספר הצלעות העוברות בו. מסומנת [math]\displaystyle{ d(v) }[/math] או [math]\displaystyle{ d_G(v) }[/math].
  • הדרגה המקסימלית: [math]\displaystyle{ \Delta(G):=\max\{d_G(v):\ v\in V(G)\} }[/math].
  • הדרגה המינימלית: [math]\displaystyle{ \delta(G):=\min\{d_G(v):\ v\in V(G)\} }[/math].
  • דרגות החוץ והפנים של קודקוד בגרף מכוון הן [math]\displaystyle{ d_G^+(v):=|\{(v,u)\in E:\ u\in V\}|,\ d_G^-(v):=|\{(u,v)\in E:\ u\in V\}| }[/math] בהתאמה, כלומר מספר הצלעות היוצאות ומספר הצלעות הנכנסות לקודקוד בהתאמה.
• איחוד של גרפים פשוטים [math]\displaystyle{ G,H }[/math] הוא [math]\displaystyle{ G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big) }[/math]. באותו אופן מוגדר איחוד זר.
• קבוצת השכנים של קודקוד [math]\displaystyle{ v }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ N_G(v):=\{u:\ (v,u)\in E(G)\} }[/math]. אם [math]\displaystyle{ A\subseteq V(G) }[/math] אז [math]\displaystyle{ N_G(A):=\bigcup_{v\in A}N_G(v)=\{u:\ \exists v\in A:\ (u,v)\in E(G)\} }[/math].

סוגי גרפים נפוצים

• גרף ריק [math]\displaystyle{ N_n }[/math] הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ומידתו 0.
• גרף מלא/שלם [math]\displaystyle{ K_n }[/math] הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ובין כל שני קודקודים יש צלע אחת בדיוק.
  • קליקה בגרף היא תת־גרף מלא.
  • מספר הקליקה של גרף [math]\displaystyle{ G }[/math] מסומן [math]\displaystyle{ \omega(G) }[/math] ושווה לסדר המקסימלי של קליקה ב־[math]\displaystyle{ G }[/math].
• מסילה [math]\displaystyle{ P_n }[/math] היא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\} }[/math].
• מעגל [math]\displaystyle{ C_n }[/math] ([math]\displaystyle{ n\ge3 }[/math]) הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\}\cup\{(v_n,v_1)\} }[/math].
  • מותן (girth) של גרף [math]\displaystyle{ G }[/math] הוא אורך המעגל הקטן ביותר בגרף, ומסומן [math]\displaystyle{ g(G) }[/math]. אם אין בגרף מעגלים (יער) אז [math]\displaystyle{ g(G)=\infty }[/math].
• גרף d־רגולרי הוא גרף שבו דרגת כל קודקוד היא [math]\displaystyle{ d }[/math].
  • גרף d⁺־רגולרי הוא גרף מכוון שבו דרגת החוץ של כל קודקוד היא [math]\displaystyle{ d }[/math]. באותו אופן מגדירים גרף [math]\displaystyle{ d^- }[/math]־רגולרי.
• גרף דו־צדדי (דו״צ) הוא גרף פשוט [math]\displaystyle{ G }[/math] שבו קיימת חלוקה [math]\displaystyle{ V(G)=V^1\uplus V^2 }[/math] כך ש־[math]\displaystyle{ E(G)\subseteq V^1\times V^2 }[/math].
  • גרף דו־צדדי מלא [math]\displaystyle{ K_{m,n} }[/math] הוא הגרף שקודקודיו הם [math]\displaystyle{ V^1\uplus V^2 }[/math] (כאשר [math]\displaystyle{ \left|V^1\right|=n,\left|V^2\right|=m }[/math]) וצלעותיו [math]\displaystyle{ V^1\times V^2 }[/math].
  • גרף r־צדדי הוא גרף [math]\displaystyle{ G }[/math] בו יש חלוקה [math]\displaystyle{ V(G)=\biguplus_{i=1}^r V^i }[/math] ל־[math]\displaystyle{ r }[/math] תתי־קבוצות כך שלכל [math]\displaystyle{ i }[/math] הקודקודים ב־[math]\displaystyle{ V^i }[/math] אינם שכנים, כלומר [math]\displaystyle{ E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j }[/math].
  • גרף r־צדדי מלא הוא גרף [math]\displaystyle{ r }[/math]־צדדי [math]\displaystyle{ G }[/math] בו [math]\displaystyle{ E(G)=\bigcup_{i\ne j}V^i\times V^j }[/math], כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.
  • גרף r־צדדי סימטרי הוא גרף [math]\displaystyle{ r }[/math]־צדדי בו [math]\displaystyle{ \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]\displaystyle{ T(n,r) }[/math] הוא הגרף ה־[math]\displaystyle{ r }[/math]־צדדי סימטרי מלא מסדר [math]\displaystyle{ n }[/math].
• גרף מסומן הוא גרף שקודקודיו סומנו ע״י [math]\displaystyle{ \{v_i\}_{i=1}^n }[/math]. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם [math]\displaystyle{ \varphi }[/math] בינהם כך ש־[math]\displaystyle{ \forall i:\ \varphi(v_i)=v_i }[/math].

עצים

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

הילוכים

• הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה [math]\displaystyle{ v_0,v_1,\dots,v_n }[/math] כך ש־[math]\displaystyle{ \forall i:\ (v_i,v_{i+1})\in E }[/math].
  • אורך ההילוך הוא [math]\displaystyle{ n }[/math] – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
  • ההילוך סגור אם [math]\displaystyle{ v_0=v_n }[/math].
• המרחק בין שני קודקודים [math]\displaystyle{ u,v }[/math] הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן [math]\displaystyle{ \operatorname{dist}_G(u,v) }[/math].
• הקוטר של גרף הוא [math]\displaystyle{ \operatorname{diameter}(G)=\max\{\operatorname{dist}_G(u,v):\ u,v\in V(G)\} }[/math].
• מסלול הוא הילוך שבו אין צלעות חוזרות.
• מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
• רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות [math]\displaystyle{ \rightarrow }[/math] המקיים [math]\displaystyle{ u\rightarrow v }[/math] אם״ם יש מסילה בין [math]\displaystyle{ u,v }[/math].
• מספר רכיבי הקשירות בגרף [math]\displaystyle{ G }[/math] יסומן [math]\displaystyle{ K(G) }[/math].
• גרף קשיר הוא גרף שבו יש רכיב קשירות אחד.
• מסלול אוילר בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
• אוילריאן הוא גרף בו קיים מסלול אוילר סגור.
• סמי־אוילריאן הוא גרף בו קיים מסלול אוילר.
• מסילה המילטוניאנית בגרף היא מסילה המכילה את כל קודקודיו.
• מעגל המילטוניאני הוא מסילה המילטוניאנית סגורה.
• המילטוניאן הוא גרף בו קיים מעגל המילטוניאני.
• הילוך אקראי: יהי [math]\displaystyle{ G }[/math] גרף לא מכוון וסופי. במצב ההתחלתי [math]\displaystyle{ p_0 }[/math] נמצאים על הקודקוד [math]\displaystyle{ v_0\in V(G) }[/math] בהסתברות 1, ובכל צעד פונים לשכן של הקודקוד הנוכחי כאשר לכל שכן הסתברות שווה. ההילוך שנוצר מקודקודים אלו נקרא הילוך אקראי.
• הסתברות החזרה בזמן [math]\displaystyle{ t }[/math] היא ההסתברות שלאחר [math]\displaystyle{ t }[/math] צעדים נהיה על הקודקוד בו התחלנו, ומסומנת [math]\displaystyle{ P_G(v_0,t) }[/math] כאשר [math]\displaystyle{ v_0 }[/math] הקודקוד ההתחלתי.
• הסתברות החזרה הממוצעת בזמן [math]\displaystyle{ t }[/math] היא [math]\displaystyle{ P_G(t):=\frac1{|V(G)|}\sum_{v\in V(G)}P_G(v,t) }[/math].

איזומורפיזם

• איזומורפיזם בין מגרף [math]\displaystyle{ G }[/math] לגרף [math]\displaystyle{ H }[/math] הוא פונקציה [math]\displaystyle{ \varphi:V(G)\to V(H) }[/math] חח״ע ועל ששומרת צלעות, כלומר [math]\displaystyle{ (u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H) }[/math] לכל [math]\displaystyle{ u,v\in V(G) }[/math]. אם קיים איזומורפיזם בין [math]\displaystyle{ G,H }[/math] אז נאמר שהם איזומורפיים ונסמן [math]\displaystyle{ G\cong H }[/math] (זה יחס שקילות).
• גרף טרנזיטיבי קודקודים הוא גרף [math]\displaystyle{ G }[/math] בו לכל [math]\displaystyle{ u,v\in V(G) }[/math] קיים אוטומורפיזם [math]\displaystyle{ \varphi:V(G)\to V(G) }[/math] כך ש־[math]\displaystyle{ \varphi(u)=v }[/math].

גרפים הנוצרים מגרפים אחרים

תת־גרף

• השמטת צלע [math]\displaystyle{ e\in E }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{e\}:=(V,E\setminus\{e\}) }[/math].
• השמטת קודקוד [math]\displaystyle{ v\in V }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\}) }[/math].
• תת־גרף הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
• תת־גרף פורש הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
• תת־גרף מושרה הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.

חלוקה

• חלוקה אלמנטרית של צלע [math]\displaystyle{ e=(u,v) }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big) }[/math].
• חלוקה של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.

כיווץ

• כיווץ של גרף [math]\displaystyle{ G }[/math] בצלע [math]\displaystyle{ e=(u,v) }[/math] הוא [math]\displaystyle{ G/e:=G\setminus\{u,v\}\cup\Big(\{e\},\{e\}\times(N_G(u)\cup N_G(v))\Big) }[/math].
• מינור של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות.
• תכונה מונוטונית של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה.

גרף משלים

• הגרף המשלים של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ \overline G:=(V,V^2\setminus E) }[/math].

גרף הקו

• גרף הקו של גרף פשוט [math]\displaystyle{ G }[/math] מסומן [math]\displaystyle{ L(G) }[/math] ומוגדר כגרף שקודקודיו הם [math]\displaystyle{ E(G) }[/math] וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־[math]\displaystyle{ G }[/math], כלומר [math]\displaystyle{ E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\} }[/math].

מכפלה קרטזית של גרפים

• המכפלה הקרטזית של הגרפים [math]\displaystyle{ G,H }[/math] היא גרף המסומן כ־[math]\displaystyle{ G\times H }[/math]. קודקודיו הם [math]\displaystyle{ V(G)\times V(H) }[/math] (כשהקודקודים הם זוגות סדורים) וצלעותיו [math]\displaystyle{ \Big((v,u_1),(v,u_2)\Big) }[/math] כאשר [math]\displaystyle{ v\in V(G)\ \and\ (u_1,u_2)\in E(H) }[/math] או [math]\displaystyle{ \Big((v_1,u),(v_2,u)\Big) }[/math] כאשר [math]\displaystyle{ u\in V(H)\ \and\ (v_1,v_2)\in E(G) }[/math].
• קובייה n־מימדית היא [math]\displaystyle{ K_2^{\times n}:=\prod_{i=1}^n K_2 }[/math].

שיכון

• שיכון של גרף [math]\displaystyle{ G }[/math] ב־[math]\displaystyle{ \mathbb R^n }[/math] הוא העתקה חח״ע [math]\displaystyle{ \varphi:V(G)\to\mathbb R^n }[/math]. כל צלע [math]\displaystyle{ (u,v)\in E(G) }[/math] מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־[math]\displaystyle{ \varphi(u) }[/math] ל־[math]\displaystyle{ \varphi(v) }[/math].
• שיכון נאות הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־[math]\displaystyle{ \mathbb R^n }[/math] חותכות זו את זו רק בתמונות של קודקודי הגרף.
• גרף מישורי הוא גרף שניתן לשיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math].
• פאה של שיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math] היא רכיב קשירות ב־[math]\displaystyle{ \mathbb R^2 }[/math] לאחר שהוציאו ממנו את התמונה של השיכון.
• גרף חוץ־מישורי הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.

גופים אפלטוניים

• 

  טטרהדרון

• 

  הקסהדרון

• 

  אוקטהדרון

• 

  דודקהדרון

• 

  איקוסהדרון

• גוף אפלטוני הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים. הגופים האפלטונים הם הטטרהדרון ([math]\displaystyle{ K_4 }[/math]), ההקסהדרון (קובייה, [math]\displaystyle{ K_2^{\times3} }[/math]), האוקטהדרון ([math]\displaystyle{ K_{2,4} }[/math]), הדודקהדרון והאיקוסהדרון.
• פאון דואלי של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.

צביעה

• k־צביעת קודקודים או k־צביעה בגרף [math]\displaystyle{ G }[/math] ללא לולאות היא פונקציה [math]\displaystyle{ f:V(G)\to[k] }[/math].
• k־צביעה כשרה היא [math]\displaystyle{ k }[/math]־צביעה [math]\displaystyle{ f }[/math] שבה לכל צלע [math]\displaystyle{ (u,v) }[/math] מתקיים [math]\displaystyle{ f(u)\ne f(v) }[/math]. כלומר, קודקודים שכנים צבועים בצבעים שונים.
• מספר הצביעה או המספר הכרומטי של גרף [math]\displaystyle{ G }[/math] מסומן כ־[math]\displaystyle{ \chi(G) }[/math] ומוגדר כ־[math]\displaystyle{ k }[/math] המינימלי עבורו קיימת [math]\displaystyle{ k }[/math]־צביעה כשרה.
• גרף k־צביע הוא גרף שקיימת לו [math]\displaystyle{ k }[/math]־צביעה כשרה, כלומר [math]\displaystyle{ \chi\le k }[/math].
• פולינום הצביעה בגרף פשוט וסופי מסומן [math]\displaystyle{ f_G }[/math]. לכל [math]\displaystyle{ x }[/math] טבעי [math]\displaystyle{ f_G(x) }[/math] מוגדר כמספר ה־[math]\displaystyle{ x }[/math]־צביעות הכשרות. לשאר ה־[math]\displaystyle{ x }[/math]־ים [math]\displaystyle{ f_G(x) }[/math] הוא ההשלמה של [math]\displaystyle{ f_G }[/math] לפולינום.
• k־צביעת צלעות בגרף [math]\displaystyle{ G }[/math] היא פונקציה [math]\displaystyle{ f:E(G)\to[k] }[/math].
• k־צביעת צלעות כשרה היא [math]\displaystyle{ k }[/math]־צביעת צלעות בה אם לשתי צלעות יש קודקוד משותף אז הן צבועות בצבעים שונים.
• אינדקס הצביעה [math]\displaystyle{ i(G) }[/math] של גרף [math]\displaystyle{ G }[/math] הוא ה־[math]\displaystyle{ k }[/math] המינימלי עבורו קיימת [math]\displaystyle{ k }[/math]־צביעת צלעות כשרה.

שידוך

• שידוך בגרף [math]\displaystyle{ G }[/math] הוא התאמה חח״ע ועל [math]\displaystyle{ f:A\to B }[/math] כאשר [math]\displaystyle{ A\uplus B\subseteq V(G) }[/math] ו־[math]\displaystyle{ \forall u\in A:\ (u,f(u))\in E(G) }[/math].
• שידוך מושלם [math]\displaystyle{ f:A\to B }[/math] הוא שידוך בו [math]\displaystyle{ A\uplus B=V(G) }[/math].
• שידוך מלא מ־[math]\displaystyle{ V^1 }[/math] ל־[math]\displaystyle{ V^2 }[/math] בגרף [math]\displaystyle{ G }[/math] דו־צדדי ש־[math]\displaystyle{ V^1,V^2 }[/math] הם צדדיו הינו התאמה חח״ע (לאו דווקא על) [math]\displaystyle{ f:V^1\to V^2 }[/math] כך ש־[math]\displaystyle{ \forall u\in V^1:\ (u,f(u))\in E(G) }[/math].

אי־תלות

• קבוצה בלתי־תלויה של צלעות בגרף [math]\displaystyle{ G }[/math] היא תת־קבוצה של [math]\displaystyle{ E(G) }[/math] שבה אין שתי צלעות בעלות קודקוד משותף.
• קבוצה בלתי־תלויה של קודקודים בגרף [math]\displaystyle{ G }[/math] היא תת־קבוצה של [math]\displaystyle{ V(G) }[/math] שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
• [math]\displaystyle{ \alpha(G) }[/math] הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־[math]\displaystyle{ G }[/math].

בעיות קיצון

• בעיית טורן: בהנתן גרף [math]\displaystyle{ H }[/math] (או קבוצת גרפים [math]\displaystyle{ \mathbb H }[/math]) ומספר טבעי [math]\displaystyle{ n }[/math] יש למצוא את המידה המקסימלית האפשרית בגרף פשוט מסדר [math]\displaystyle{ n }[/math] שאין לו תת־גרף איזומורפי ל־[math]\displaystyle{ H }[/math] (או לאחד מהגרפים ב־[math]\displaystyle{ \mathbb H }[/math]). מספר זה מסומן כ־[math]\displaystyle{ \operatorname{ex}(n,H) }[/math] או [math]\displaystyle{ \operatorname{ex}(n,\mathbb H) }[/math] וגרף כזה נקרא גרף מרבי נמנע [math]\displaystyle{ H }[/math] (או [math]\displaystyle{ \mathbb H }[/math]).
• מספר רמזי [math]\displaystyle{ R(s,t) }[/math] הוא הסדר המינימלי כך שאם [math]\displaystyle{ G }[/math] גרף מסדר זה אז [math]\displaystyle{ K_s }[/math] תת־גרף של [math]\displaystyle{ G }[/math] או ש־[math]\displaystyle{ K_t }[/math] תת־גרף של [math]\displaystyle{ \overline G }[/math].

תורת הגרפים האלגברית

• מטריצת השכנות של גרף סופי [math]\displaystyle{ G }[/math] (מכוון או לא) כך ש־[math]\displaystyle{ V=\{v_i\}_{i=1}^n }[/math] היא [math]\displaystyle{ A_G\in\mathbb N_0^{n\times n} }[/math] שבה [math]\displaystyle{ a_{ij} }[/math] הוא מספר הצלעות מ־[math]\displaystyle{ v_i }[/math] ל־[math]\displaystyle{ v_j }[/math].
• נסמן [math]\displaystyle{ \operatorname{spec}(A_G)=\operatorname{spec}(G) }[/math] כרב־קבוצה של הע״ע של [math]\displaystyle{ A_G }[/math] (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).
• מטריצת הדרגות של גרף [math]\displaystyle{ G }[/math] מסדר [math]\displaystyle{ n }[/math] שקודקודיו [math]\displaystyle{ V(G)=\{v_i\}_{i=1}^n }[/math] היא המטריצה [math]\displaystyle{ D_G:=\Big(\delta_{ij}d_G(v_i)\Big)_{i,j=1}^n }[/math].
• הלפלסיאן של [math]\displaystyle{ G }[/math] הוא [math]\displaystyle{ L_G:=D_G-A_G }[/math].

משפטים

• [math]\displaystyle{ \sum_{v\in V}d_G(v)=2|E(G)| }[/math].
• [math]\displaystyle{ \sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E(G)| }[/math].
• אם [math]\displaystyle{ \delta(G)\ge 2 }[/math] אז יש ב־[math]\displaystyle{ G }[/math] מעגל.
• [math]\displaystyle{ g(G)\le2 }[/math] אם״ם הגרף לא פשוט.
• גרף הוא ריק אם״ם הוא 0־רגולרי.
• גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
• גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
• אם גרף סופי ופשוט הוא [math]\displaystyle{ d }[/math]־רגולרי כך ש־[math]\displaystyle{ d }[/math] אי־זוגי אזי הגרף מסדר זוגי.
• גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
• בכל עץ סופי מסדר גדול מ־1 יש עלה.
• גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
• גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
• לכל גרף קשיר וסופי קיים עץ פורש.
• משפט קיילי: יש [math]\displaystyle{ n^{n-2} }[/math] עצים מסומנים מסדר [math]\displaystyle{ n }[/math].
• משפט מטריצה–עץ/משפט עצים פורשים: כידוע, מינור [math]\displaystyle{ A[i,j] }[/math] של מטריצה [math]\displaystyle{ A }[/math] הוא המטריצה המתקבלת מהשמטת השורה ה־[math]\displaystyle{ i }[/math] והעמודה ה־[math]\displaystyle{ j }[/math]. נסמן [math]\displaystyle{ \hat A }[/math] כמינור המוחק את השורה והעמודה האחרונות. עתה יהי [math]\displaystyle{ G }[/math] גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־[math]\displaystyle{ \det\!\left(\hat L_G\right) }[/math].
• בעיית הסוכן הנוסע: נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
• ביער מסדר [math]\displaystyle{ n\in\mathbb N }[/math] עם [math]\displaystyle{ k }[/math] רכיבי קשירות יש [math]\displaystyle{ n-k }[/math] צלעות.
• גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_3 }[/math].
• כל מסילה היא מסלול.
• קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
• גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
• משפט אוילר: גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
• גרף [math]\displaystyle{ G }[/math] קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
• משפט דיראק: יהי [math]\displaystyle{ G }[/math] גרף פשוט מסדר [math]\displaystyle{ n }[/math]. אם [math]\displaystyle{ \delta(G)\ge\frac n2 }[/math] אז [math]\displaystyle{ G }[/math] המילטוניאן.
• אם [math]\displaystyle{ G\cong H }[/math] אז הפרמטרים הבאים שווים:
  • סדר: [math]\displaystyle{ |V(G)|=|V(H)| }[/math].
  • מידה: [math]\displaystyle{ |E(G)|=|E(H)| }[/math].
  • מספר רכיבי הקשירות: [math]\displaystyle{ K(G)=K(H) }[/math].
  • וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
  • קוטר: [math]\displaystyle{ \operatorname{diameter}(G)=\operatorname{diameter}(H) }[/math].
• [math]\displaystyle{ G\cong H }[/math] אם״ם [math]\displaystyle{ \overline G\cong\overline H }[/math].
• [math]\displaystyle{ L(P_n)\cong P_{n-1},L(C_n)\cong C_n }[/math].
• הקובייה ה־[math]\displaystyle{ n }[/math] מימדית [math]\displaystyle{ K_2^{\times n} }[/math] איזומורפית ל־[math]\displaystyle{ B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\}) }[/math] ול־[math]\displaystyle{ H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\}) }[/math].
• לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־[math]\displaystyle{ \mathbb R^3 }[/math] כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, [math]\displaystyle{ \forall i:\ \varphi(v_i)=(i,i^2,i^3) }[/math] כאשר [math]\displaystyle{ V=\{v_i\}_{i=1}^n }[/math].
• משפט הפאון של אוילר: לכל גרף מישורי סופי קשיר מסדר [math]\displaystyle{ n }[/math] וממידה [math]\displaystyle{ m }[/math] מספר הפאות [math]\displaystyle{ f }[/math] לא תלוי בשיכון הנאות ומקיים [math]\displaystyle{ n-m+f=2 }[/math].
• יהי [math]\displaystyle{ G }[/math] גרף פשוט וקשיר מסדר [math]\displaystyle{ n\ge3 }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le3n-6 }[/math].
• יהי [math]\displaystyle{ G }[/math] פשוט וקשיר מסדר [math]\displaystyle{ n }[/math] ומותן [math]\displaystyle{ g\lt \infty }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le g\frac{n-2}{g-2} }[/math].
• לכל גרף מישורי פשוט סופי [math]\displaystyle{ G }[/math] מתקיים [math]\displaystyle{ \delta(G)\le5 }[/math].
• משפט קורטובסקי: גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של [math]\displaystyle{ K_5 }[/math] או של [math]\displaystyle{ K_{3,3} }[/math].
• גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_4 }[/math] או ל־[math]\displaystyle{ K_{2,3} }[/math].
• השערת וגנר: כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של [math]\displaystyle{ G }[/math] אם״ם הוא אינו מקיים את התכונה.
• משפט רוברטסון–סימור: השערת וגנר נכונה.
• הגרף של כל גוף אפלטוני הוא מישורי.
• לכל גרף [math]\displaystyle{ G }[/math] פשוט [math]\displaystyle{ 1\le\chi(G)\le|V(G)| }[/math]. [math]\displaystyle{ \chi(G)=1 }[/math] אם״ם [math]\displaystyle{ G }[/math] גרף ריק ו־[math]\displaystyle{ \chi(G)=|V(G)| }[/math] אם״ם הוא גרף מלא.
• משפט ברוקס: לכל גרף [math]\displaystyle{ G }[/math] פשוט וסופי [math]\displaystyle{ \chi(G)\le\Delta(G)+1 }[/math] ושוויון מתקיים אם״ם [math]\displaystyle{ \omega(G)=\Delta(G)+1 }[/math] או אם [math]\displaystyle{ G }[/math] איחוד זר של מעגלים ומסילות ויש מעגל מסדר אי־זוגי.
• יהא [math]\displaystyle{ G }[/math] פשוט וסופי. [math]\displaystyle{ \chi(G)\le2 }[/math] אם״ם אין ב־[math]\displaystyle{ G }[/math] מעגלים מאורך אי־זוגי.
• גרף הוא 2־צביע אם״ם הוא דו־צדדי.
• בעיית 4 הצבעים: לכל גרף מישורי סופי פשוט [math]\displaystyle{ G }[/math] הוא 4־צביע.
• [math]\displaystyle{ 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]\displaystyle{ \forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x) }[/math].
• [math]\displaystyle{ f_G }[/math] פולינום מתוקן ודרגתו [math]\displaystyle{ |V(G)| }[/math].
• [math]\displaystyle{ \chi(G)=\max\{x\in\mathbb N_0:\ f_G(x)=0\}+1 }[/math].
• משפט סטנלי: מספר ההכוונות הלא מעגליות של [math]\displaystyle{ G }[/math] הוא [math]\displaystyle{ (-1)^n f_G(-1) }[/math].
• לכל גרף [math]\displaystyle{ G }[/math] סופי [math]\displaystyle{ \Delta(G)\le i(G) }[/math]. אם הוא לא ריק אז [math]\displaystyle{ i(G)\le2\Delta(G)-1 }[/math].
• אם [math]\displaystyle{ G }[/math] דו־צדדי ו־[math]\displaystyle{ d }[/math]־רגולרי אז [math]\displaystyle{ i(G)=d }[/math].
• אם [math]\displaystyle{ f:A\to B }[/math] שידוך אז [math]\displaystyle{ \{(u,f(u)):\ u\in A\} }[/math] קבוצה בלתי־תלויה.
• משפט הול (Hall): לכל גרף דו־צדדי שצדדיו [math]\displaystyle{ V^1,V^2 }[/math] קיים שידוך מלא מ־[math]\displaystyle{ V^1 }[/math] ל־[math]\displaystyle{ V^2 }[/math] אם״ם [math]\displaystyle{ \forall A\subseteq V^1:\ |N_G(A)|\ge|A| }[/math].
• משפט טורן: הגרף המרבי נמנע [math]\displaystyle{ K_r }[/math] היחיד מסדר [math]\displaystyle{ n }[/math] הוא [math]\displaystyle{ T(n,r-1) }[/math].
• אם [math]\displaystyle{ r\mid n }[/math] אז [math]\displaystyle{ T(n,r) }[/math] הוא [math]\displaystyle{ \left(n-\frac nr\right) }[/math]־רגולרי ו־[math]\displaystyle{ \operatorname{ex}(n,K_{n+1})=\frac{n^2}2\left(1-\frac1r\right) }[/math].
• למת לחיצות הידיים: עבור כל גרף פשוט מסדר 6 או ש־[math]\displaystyle{ G }[/math] מכיל משולש או ש־[math]\displaystyle{ \overline G }[/math] מכיל משולש. (למעשה, [math]\displaystyle{ R(3,3)=6 }[/math].)
• [math]\displaystyle{ R(1,t)=1\ \and\ R(2,t)=t\ \and\ R(s,t)=R(t,s) }[/math] ואם [math]\displaystyle{ t,s\ge3 }[/math] אז [math]\displaystyle{ R(s,t)\le R(s-1,t)+R(s,t-1) }[/math].
• [math]\displaystyle{ R(s,t)\le\binom{s+t-2}{s-1} }[/math].
• אם [math]\displaystyle{ G }[/math] לא מכוון אז [math]\displaystyle{ A_G }[/math] סימטרית.
• לכל גרף סופי מתקיים [math]\displaystyle{ \sum_{i=1}^n a_{ij}=d_G^-(v_j)\ \and\ \sum_{j=1}^n a_{ij}=d_G^+(v_i) }[/math].
• העקבה [math]\displaystyle{ \operatorname{tr}(A_G) }[/math] היא מספר הלולאות ב־[math]\displaystyle{ G }[/math].
• יהי [math]\displaystyle{ G }[/math] פשוט ולא מכוון. אזי [math]\displaystyle{ \operatorname{tr}\!\left(A_G^2\right)=2|E(G)| }[/math].
• יהי [math]\displaystyle{ G }[/math] לא מכוון. אזי [math]\displaystyle{ |E(G)|=\sum_{i\le j}a_{ij} }[/math].
• מספר ההילוכים מ־[math]\displaystyle{ v_i }[/math] ל־[math]\displaystyle{ v_j }[/math] מאורך [math]\displaystyle{ t }[/math] הוא [math]\displaystyle{ (A_G^t)_{i,j} }[/math].
• מספר ההילוכים הסגורים מאורך [math]\displaystyle{ t }[/math] ב־[math]\displaystyle{ G }[/math] הוא [math]\displaystyle{ \operatorname{tr}\!\left(A_G^t\right) }[/math] (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).
• אם [math]\displaystyle{ G,H }[/math] סופיים ולא מכוונים אז [math]\displaystyle{ \operatorname{spec}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H) }[/math].
• אם [math]\displaystyle{ G }[/math] גרף [math]\displaystyle{ d }[/math]־רגולרי אז [math]\displaystyle{ d\in\operatorname{spec}(G) }[/math] וו״ע מתאימים הם [math]\displaystyle{ v_A=(I_A(v_i))_{i=1}^n }[/math] לכל רכיב קשירות [math]\displaystyle{ A\subseteq V(G)=\{v_i\}_{i=1}^n }[/math].
• יהא [math]\displaystyle{ G }[/math] סופי ולא מכוון. [math]\displaystyle{ G }[/math] דו־צדדי אם״ם מתקיים התנאי הבא: [math]\displaystyle{ \lambda }[/math] ע״ע של [math]\displaystyle{ A_G }[/math] מריבוי אלגברי [math]\displaystyle{ k }[/math] אם״ם [math]\displaystyle{ -\lambda }[/math] ע״ע מאותו ריבוי.
• הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.
• הלפלסיאן של גרף לא מכוון הוא מטריצה סימטרית.
• הלפלסיאן אינו מטריצה הפיכה.
• אם [math]\displaystyle{ G }[/math] לא מכוון סופי אז [math]\displaystyle{ \operatorname{rank}(L_G)=|V(G)|-K(G) }[/math].
• בגרף טרנזיטיבי קודקודים [math]\displaystyle{ \forall v\in V(G):\ P_G(v,t)=P_G(t) }[/math].
• יהא [math]\displaystyle{ G }[/math] לא מכוון, סופי ו־[math]\displaystyle{ d }[/math]־רגולרי מסדר [math]\displaystyle{ n }[/math]. אזי [math]\displaystyle{ \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].