Некоторые задачи, связанные с определением существования определённых типов графов:

• Доказательство, что во всяком графе, в котором есть хотя бы две вершины, найдутся две вершины одинаковой степени. 2
• Доказательство, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2. 2
• Доказательство, что при любых 0 k n таких, что kn чётное, существует граф на n вершинах, степени которого равны k. 2
• Доказательство, что в дереве k листьев и нет вершин степени 2, то количество вершин дерева меньше 2k. 2

Также к задачам, связанным с графами, относятся, например, нахождение кратчайших маршрутов в графе (например, от заданной начальной вершины ко всем другим или между всеми парами вершин графа). 3