Некоторые основные характеристики графов с разным числом рёбер и вершин:

• Степень вершины — количество рёбер, для которых она является концевой (при этом петли считают дважды). 1
• Изолированная вершина — не является концом ни для одного ребра. 14
• Висячая вершина — из неё выходит ровно одно ребро. 14
• Полный граф — содержит все возможные для этого типа рёбра при неизменном множестве вершин. 1
• Эйлеров граф — в нём можно обойти все вершины и при этом пройти одно ребро только один раз. 1 В таком графе каждая вершина должна иметь только чётное число рёбер. 1
• Цикломатическое число — наименьшее число рёбер, удаление которых приводит к графу без циклов. 2
• Число вершинной связности — наименьшее количество вершин, удаление которых приводит к несвязному графу или тривиальному графу (состоящему из одной вершины). 2
• Хроматическое число — наименьшее количество цветов, которыми можно раскрасить вершины (рёбра) графа так, чтобы любые смежные вершины (рёбра) были окрашены разными цветами. 2
• Число внешней устойчивости — наименьшее количество вершин такого подмножества множества вершин графа, что любая вершина, не принадлежащая этому подмножеству, смежна по крайней мере с одной вершиной из него. 2