Оценка числа графов

Лемма 1. > число Непера).

Доказательство. Проведём индукцию по n. При имеем > . Пусть > . Тогда (k + 1)! > > , так как > , что в свою очередь следует из известного неравенства > .■

Лемма 2. .

Доказательство. .■

ТЕОРЕМА. Пусть – число всех попарно неизоморфных графов с h рёбрами без изолированных вершин. Тогда < .

Доказательство. Граф с h рёбрами имеет не более 2 h вершин. Занумеруем вершины графа числами 1, 2, …. Число пар вершин, которые могут связываться рёбрами, не превосходит величины

.

Из r рёбер графа с h рёбрами можно построить не более графов, т.е.

< ■