Дискретна математика и теория на графите - много трудни задачи с решения

Решение:
Разглеждаме графа, чиито върхове са градовете, а ребрата са директните линии. Всеки връх има степен най-много [tex]3[/tex], а всеки два върха са на разстояние най-много [tex]2[/tex] (най-много едно прекачване означава най-много два полета).
Горна граница. Фиксираме град [tex]v[/tex]. Всеки друг град е или съсед на [tex]v[/tex], или съсед на съсед на [tex]v[/tex]. Градът [tex]v[/tex] има най-много [tex]3[/tex] съседа, а всеки от тях има най-много [tex]2[/tex] съседа, различни от [tex]v[/tex]. Следователно броят на градовете е най-много
[tex]1+3+3\cdot 2=10[/tex]
Пример с [tex]10[/tex] града (графът на Петерсен): градовете са [tex]\binom{5}{2}=10[/tex]-те двуелементни подмножества на [tex]\{1,2,3,4,5\}[/tex], като два града са свързани, ако съответните подмножества не се пресичат. Подмножеството [tex]\{a,b\}[/tex] не се пресича с точно [tex]\binom{3}{2}=3[/tex] подмножества, затова всяка степен е [tex]3[/tex].
Две различни подмножества, които се пресичат, имат точно един общ елемент, например [tex]\{a,b\}[/tex] и [tex]\{a,c\}[/tex]; останалите два елемента [tex]d,e[/tex] образуват подмножеството [tex]\{d,e\}[/tex], което не се пресича с нито едно от двете, затова тези два града са свързани с едно прекачване. Следователно [tex]10[/tex] града са възможни и отговорът е [tex]10[/tex].

Решение:
Факт [tex]1[/tex]: реброто [tex]e=xy[/tex] е мост тогава и само тогава, когато не лежи на никакъв цикъл. Ако [tex]e[/tex] лежи на цикъл [tex]C[/tex], всеки маршрут през [tex]e[/tex] може да се пренасочи по пътя [tex]C-e[/tex], затова премахването на [tex]e[/tex] не разделя нищо. Обратно, ако [tex]e[/tex] не е мост, то [tex]x[/tex] и [tex]y[/tex] се свързват с път в [tex]G-e[/tex], и този път заедно с [tex]e[/tex] образува цикъл.
Факт [tex]2[/tex]: премахването на мост [tex]e=xy[/tex] увеличава броя на компонентите с точно [tex]1[/tex]. Наистина, променя се само компонентата, съдържаща [tex]e[/tex], и всеки неин връх [tex]w[/tex] се свързва с [tex]x[/tex] в [tex]G[/tex] с път; ако прекъснем този път при първото минаване през [tex]e[/tex] (ако има такова), получаваме път в [tex]G-e[/tex] от [tex]w[/tex] до [tex]x[/tex] или до [tex]y[/tex]. Значи тази компонента се разпада на най-много две части, и то точно на две, защото [tex]e[/tex] е мост.
Сега нека [tex]B[/tex] е множеството на мостовете на [tex]G[/tex] и [tex]H=G-B[/tex] (същите върхове, без мостовете).
Стъпка [tex]1[/tex]: [tex]c(H)=c(G)+|B|[/tex]. Премахваме мостовете един по един. Премахването на ребра не създава нови цикли, затова според факт [tex]1[/tex] всяко останало ребро от [tex]B[/tex] е мост и на текущия граф, а според факт [tex]2[/tex] всяко премахване увеличава броя на компонентите с точно [tex]1[/tex].
Стъпка [tex]2[/tex]: компонентите на [tex]H[/tex] са точно двусвързаните компоненти на [tex]G[/tex].
Всяка компонента [tex]K[/tex] на [tex]H[/tex] е двусвързана. Нека [tex]e[/tex] е ребро на [tex]K[/tex]. То не е мост, затова според факт [tex]1[/tex] лежи на някакъв цикъл [tex]C[/tex] на [tex]G[/tex]. Нито едно ребро на [tex]C[/tex] не е мост (всяко от тях лежи на [tex]C[/tex]), затова [tex]C\subseteq H[/tex], а тъй като [tex]C[/tex] е свързан и съдържа [tex]e[/tex], имаме [tex]C\subseteq K[/tex]. Като заменим [tex]e[/tex] с пътя [tex]C-e[/tex] във всеки маршрут в [tex]K[/tex], виждаме, че [tex]K-e[/tex] е свързан.
Всеки двусвързан подграф [tex]S[/tex] на [tex]G[/tex] се съдържа в една компонента на [tex]H[/tex]. Ако [tex]S[/tex] съдържаше мост [tex]e=xy[/tex], то [tex]S-e[/tex] би бил свързан, т.е. [tex]x[/tex] и [tex]y[/tex] биха били свързани в [tex]G-e[/tex] и [tex]e[/tex] би лежало на цикъл, което противоречи на факт [tex]1[/tex]. Следователно [tex]S\subseteq H[/tex], а понеже е свързан, [tex]S[/tex] се съдържа в една компонента на [tex]H[/tex].
От тези две твърдения следва, че всяка компонента на [tex]H[/tex] е максимален двусвързан подграф на [tex]G[/tex], а всеки максимален двусвързан подграф се съдържа в компонента на [tex]H[/tex] и следователно съвпада с нея (изолираните върхове на [tex]H[/tex] са компоненти с по един връх). Следователно
[tex]c_2(G)=c(H)=c(G)+|B|\ \Rightarrow\ |\mathrm{br}(G)|=c_2(G)-c(G)[/tex]

Решение:
Нека [tex]n=10[/tex], [tex]m=26[/tex], [tex]t[/tex] е броят на триъгълниците, [tex]d(v)[/tex] е степента на върха [tex]v[/tex], а [tex]N(v)[/tex] е множеството на съседите му. Триъгълниците, съдържащи реброто [tex]xy[/tex], са [tex]xyz[/tex] със [tex]z\in N(x)\cap N(y)[/tex], а всеки триъгълник има [tex]3[/tex] ребра, затова
[tex]3t=\sum_{xy\in E}|N(x)\cap N(y)|[/tex]
Тъй като [tex]N(x)\cup N(y)\subseteq V[/tex], по принципа на включването и изключването
[tex]|N(x)\cap N(y)|=d(x)+d(y)-|N(x)\cup N(y)|\ge d(x)+d(y)-n[/tex]
Като сумираме по всички ребра, получаваме [tex]3t\ge\sum_{xy\in E}\left(d(x)+d(y)\right)-mn[/tex]. В тази сума всеки връх [tex]v[/tex] участва в [tex]d(v)[/tex] ребра и всеки път дава [tex]d(v)[/tex], затова сумата е равна на [tex]\sum_{v\in V}d(v)^2[/tex]. От неравенството на Коши-Буняковски и лемата за ръкостисканията
[tex]\sum_{v\in V}d(v)^2\ge\frac{1}{n}\left(\sum_{v\in V}d(v)\right)^2=\frac{(2m)^2}{n}[/tex]
Следователно
[tex]3t\ge\frac{4m^2}{n}-mn=\frac{4\cdot 676}{10}-260=270{,}4-260=10{,}4[/tex]
откъдето [tex]t\ge\frac{10{,}4}{3}\gt 3[/tex]. Тъй като [tex]t[/tex] е цяло число, [tex]t\ge 4[/tex].

Решение:
Разглеждаме графа, чиито върхове са хората, а ребрата са приятелствата: всеки два различни върха имат точно един общ съсед. Нека [tex]n[/tex] е броят на върховете; при [tex]n=1[/tex] твърдението е вярно, затова нека [tex]n\ge 2[/tex].
Стъпка [tex]1[/tex]: всяка степен е четна. Нека [tex]v[/tex] е връх и [tex]u\in N(v)[/tex], където [tex]N(v)[/tex] е множеството на съседите на [tex]v[/tex]. Двойката [tex]u,v[/tex] има точно един общ съсед [tex]u'[/tex]; той принадлежи на [tex]N(v)[/tex] и [tex]u'\ne u[/tex]. Общият съсед на [tex]u'[/tex] и [tex]v[/tex] е [tex]u[/tex], затова изображението [tex]u\mapsto u'[/tex] е инволюция на [tex]N(v)[/tex] без неподвижни точки. То разбива [tex]N(v)[/tex] на двойки [tex]\{u,u'\}[/tex], следователно степента [tex]d(v)=|N(v)|[/tex] е четна.
Стъпка [tex]2[/tex]: фиксираме връх [tex]v[/tex] и полагаме [tex]W=V\setminus\left(N(v)\cup\{v\}\right)[/tex], т.е. [tex]|W|=n-1-d(v)[/tex]. Връх [tex]u\in N(v)[/tex] е съседен на [tex]v[/tex], на [tex]u'[/tex] и на никой друг връх от [tex]N(v)[/tex] (друг такъв би бил втори общ съсед на [tex]u[/tex] и [tex]v[/tex]), затова [tex]u[/tex] има точно [tex]d(u)-2[/tex] съседа в [tex]W[/tex]. Всеки връх [tex]w\in W[/tex] има точно един общ съсед с [tex]v[/tex], т.е. точно един съсед в [tex]N(v)[/tex]. Като преброим ребрата между [tex]N(v)[/tex] и [tex]W[/tex] по два начина, получаваме
[tex]n-1-d(v)=|W|=\sum_{u\in N(v)}\left(d(u)-2\right)[/tex]
Според стъпка [tex]1[/tex] дясната страна е четна и [tex]d(v)[/tex] е четно, затова [tex]n-1[/tex] е четно, т.е. [tex]n[/tex] е нечетно. (Пример: [tex]k[/tex] триъгълника с общ връх дават такава група от [tex]2k+1[/tex] души.)

Решение:
Нека [tex]H[/tex] е графът на „непознатите“: двама души са съседни в [tex]H[/tex], ако не се познават. Тъй като всеки има един и същ брой [tex]d[/tex] познати, [tex]H[/tex] е регулярен от степен [tex]s=n-1-d[/tex], като [tex]s\ge 1[/tex], защото има двама непознати. Останалите хора образуват множество [tex]S[/tex] без ребра на [tex]H[/tex] вътре в него (независимо множество в [tex]H[/tex]).
Да преброим ребрата на [tex]H[/tex] между [tex]S[/tex] и [tex]V\setminus S[/tex]. Всеки връх от [tex]S[/tex] има всичките си [tex]s[/tex] съседа извън [tex]S[/tex], което дава точно [tex]s|S|[/tex] ребра; всеки връх извън [tex]S[/tex] има най-много [tex]s[/tex] съседа в [tex]S[/tex], което дава най-много [tex]s(n-|S|)[/tex] ребра. Следователно, понеже [tex]n[/tex] е нечетно,
[tex]s|S|\le s(n-|S|)\ \Rightarrow\ |S|\le\frac{n}{2}\ \Rightarrow\ |S|\le\frac{n-1}{2}[/tex]
Значи от всяка такава компания трябва да си тръгнат поне [tex]n-\frac{n-1}{2}=\frac{n+1}{2}[/tex] души.
Пример, в който това е достатъчно: [tex]n[/tex]-те души седят около кръгла маса и всеки познава всички освен двамата си съседи на масата. Всеки има [tex]n-3[/tex] познати и има хора, които не се познават. Хората на местата [tex]1,3,5,\ldots,n-2[/tex] (това са [tex]\frac{n-1}{2}[/tex] души, никои двама от които не са съседи) се познават всеки с всеки, затова е достатъчно да си тръгнат останалите [tex]\frac{n+1}{2}[/tex] души. Следователно
[tex]k=\frac{n+1}{2}[/tex]