Граф є зв'язним, якщо будь-які його вершини можна сполучити шляхом. Кількості вершин, ребер та компонент зв'язності позначаються відповідно. 12. Граф є підграфом графа якщо кожна вершина графа є вершиною графа і кожне ребро графа є ребром графа При цьому дві вершини , сполучені ребром у не обов'язково сполучені ребром у .