Дискретная математика и теория графов - очень сложные задачи с решениями

Решение:
Рассмотрим граф, вершины которого — города, а рёбра — прямые линии. Степень каждой вершины не больше [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]