Граф – це геометрична фігура, яка складається з точок та ліній, що їх з'єднують. Крапки називають вершинами графа, а лінії – Ребрами. Два ребра називаються суміжними, якщо вони мають загальна вершина. Два ребра називаються кратними, якщо вони з'єднують одну і ту ж пару вершин.
Доказ: Кількість ребер графа дорівнює половині суми ступенів його вершин. Оскільки кількість ребер має бути цілим числом, то сума ступенів вершин має бути парною. А це можливо лише в тому випадку, якщо граф містить парне число непарних вершин.
| Повний граф | |
|---|---|
| K7, повний граф з 7 вершинами | |
| Вершин | n |
| Ребер | |
| Діаметр | 1 |
Вага ребра — значення, поставлене у відповідність до цього ребру зваженого графа. Зазвичай вага — речове число, у такому разі його можна інтерпретувати як «довжину» ребра. Зважений граф — графкожному ребру якого поставлено у відповідність певне значення (вага ребра).