Доказательство. Если у нас есть р вершин, то число различных графов, построенных на этом множестве вершин будет равно

Если у нас есть р вершин, то число различных графов, построенных на этом множестве вершин будет равно . р² – это число всех возможных пар вершин графа с р вершинами или всех возможных ребер. Поскольку наш граф без петель, то удаляем все пары с одинаковыми элементами – таких пар будет р. В силу того, что граф неориентированный порядок элементов в паре не играет роли – делим на 2. Число всех возможных графов с р вершинами даст нам нужно число всех подмножеств множества, состоящего из , а это как мы знаем будет равно . Теперь рассмотрим граф с (р+1) вершинами. Эйлеров граф с (р+1) вершинами мы можем получить из графа с р вершинами, соединив (р+1) вершину со всеми остальными графами. Но Эйлеров граф мы получим не из каждого графа с р вершинами (могут быть изолированные вершин). Следовательно, число Эйлеровых графов с (р+1) вершинами . Искомое отношение: