שינויים

** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.

* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <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>.