Графы можно классифицировать по количеству рёбер и вершин следующим образом:

По количеству вершин выделяют, например:

• Пустой граф. 1 У такого графа нет вершин и рёбер. 1
• Тривиальный граф. 1 У него есть только одна вершина и нет рёбер. 1
• Регулярный граф. 1 У каждой вершины одинаковое количество соседей. 1

По количеству рёбер выделяют, например:

• Полный граф. 14 Каждая пара вершин соединена ребром. 1
• Насыщенный граф. 4 Количество рёбер близко к максимально возможному. 4
• Разреженный граф. 4 Количество рёбер близко к количеству вершин в графе. 4

Также есть понятие степени вершины — это количество рёбер, для которых она является концевой (при этом петли считают дважды). 2 Изолированная вершина не имеет рёбер (её степень равна 0). 3