графы - Сколько существует неориентированных графов с N вершинами?

Если под графом здесь подразумевается простой граф, не содержащий петель и кратных рёбер, а вершины считаются занумерованными, то таких (размеченных) графов имеется ровно $%2^{\frac{n(n-1)}2}$%.

Доказательство такое: рёбер в полном графе можно провести максимум $%\frac{n(n-1)}2$%, так как начало ребра выбирается $%n$% способами; при фиксированном начале конец ребра выбирается $%n-1$% способом, и в конце надо поделить на $%2$%, так как ребро неориентированное. Теперь занумеруем эти рёбра произвольным образом, и далее про каждое ребро последовательно решаем, проводить его в графе или не проводить. Это значит, что на каждом из шагов имеется $%2$% способа выбора, то есть в итоге получается $%2\cdot2\cdot\,\cdots\,\cdot2$%, где двойка берётся $%\frac{n(n-1)}2$% раз.