елементарен граф

даден е граф с 10 върха и 26 ребра, да се док че броя на триъгълниците е поне 3.

ХАКУНА МАТАТА - Я МИ Е НА УЮ

Тва хубаво, ама как да видим че триъгълниците са всъщност поне 5, а и да построим пример с 25 ребра и НИТО ЕДИН триъгълник?

МОЛЯ???

ХАКУНА МАТАТА - Я МИ Е НА УЮ

Тоя въпрос се третира от известната теорема на Туран за графите (виж едноименна книга на Хаджииванов), която казва че в един граф с n върха, в който няма триъгълници, максималният брой на ребрата е цялата част на
n^2/4. В нашия случай: 10^2/4=100/4=25.
С други думи, може да начертаем граф с 25 върха който няма триъгълник.
Този граф се нарича граф на Туран и се състои от два празни подграфа от 5 върха всеки, които са свързани с максималния възможен брой ребра: 5*5=25.
Ясно е от тази конструкция, че ако добавим едно (26-тото) ребро, то ще получим поне 5 триъгълника. Което обяснява забележката направена от Недев.

Повече на:
[линк]'s_theorem