Формально графова модель G(V,P) складається з двох множин – множини V об'єктів (вершин вузлів) і множини Р зв'язків (ребер). Дуги – направленні лінії (стрілки), що зв'язують компоненти між собою. Ребра – ненаправлені лінії, зо зв'язують компоненти між собою.

Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.

Ребра позначають парами вершин, наприклад (А, В), (1, 2), або малими літерами українського та латинського алфавітів.

Граф із петлями та кратними ребрами називають мультиграфом або псевдографом.

Циклом називається шлях, у якому співпадають його початкова і кінцева вершина. Простим циклом у графі називається цикл, що не проходить через жодну вершину більше одного разу. цикли, що містять: а) 4 ребра; б) 6 ребер; в) 5 ребер; г) 10 ребер.

З леми про рукостискання, доведеною Ейлером в 1736, як частини його першої роботи з теорії графів, випливає, що будь який кубічний граф має парне число вершин.

В теорії графів, ребра — це абстрактний об’єкт, що з’єднує дві вершини графу, на відміну від багатокутника і багатогранника, ребра якого мають конкретне геометричне подання у вигляді лінійного сегмента. Однак, будь-який поліедр може бути представлений у вигляді його кістяку, …