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