Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v1 и v2 графа G существует автоморфизм
В теории графов рёберно-транзитивным называется такой граф G, для двух любых рёбер которого e1 и e2 существует автоморфизм, отображающий e1 в e2.
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм:
- f : V(G) → V(G)
Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.
Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
Алгебраическая теория графов — направление в теории графов, применяющее алгебраические методы к теоретико-графовым задачам. В свою очередь, алгебраическая теория графов подразделяется на три ветви: линейно-алгебраическую, теоретико-групповую и изучающую инварианты графов.
Изогональный или вершинно транзитивный многогранник — многогранник, все вершины которого эквивалентны. В частности все вершины окружены одним и тем же видом граней в том же самом порядке и с теми же самыми углами между соответствующими гранями. Термин также может быть применён к многоугольникам или замощениям и так далее.
Теорема Роббинса, названная по имени американского математика Герберта Роббинса, утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
Кратные рёбра — это два и более рёбер, инцидентных одним и тем же двум вершинам. Простой граф кратных рёбер не имеет.
Граф Любляны — неориентированный двудольный граф с 112 вершинами и 168 рёбрами.
Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.
110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.
Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.
Пространство циклов неориентированного графа — линейное пространство над полем 
, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.
