Discrete Mathematics and Graph Theory: Very Difficult Problems with Solutions

Solution:
Consider the graph whose vertices are the cities and whose edges are the direct lines. Every vertex has degree at most [tex]3[/tex], and any two vertices are at distance at most [tex]2[/tex] (at most one change means at most two flights).
Upper bound. Fix a city [tex]v[/tex]. Every other city is either a neighbour of [tex]v[/tex] or a neighbour of a neighbour of [tex]v[/tex]. The city [tex]v[/tex] has at most [tex]3[/tex] neighbours, and each of them has at most [tex]2[/tex] neighbours other than [tex]v[/tex]. Hence the number of cities is at most
[tex]1+3+3\times 2=10[/tex]
Example with [tex]10[/tex] cities (the Petersen graph): the cities are the [tex]\binom{5}{2}=10[/tex] two-element subsets of [tex]\{1,2,3,4,5\}[/tex], and two cities are joined if the corresponding subsets are disjoint. A subset [tex]\{a,b\}[/tex] is disjoint from exactly [tex]\binom{3}{2}=3[/tex] subsets, so every degree is [tex]3[/tex].
Two different subsets that are not disjoint share exactly one element, say [tex]\{a,b\}[/tex] and [tex]\{a,c\}[/tex]; the remaining two elements [tex]d,e[/tex] form the subset [tex]\{d,e\}[/tex], which is disjoint from both, so these two cities are connected with one change. Hence [tex]10[/tex] cities are possible, and the answer is [tex]10[/tex].

Solution:
Fact [tex]1[/tex]: an edge [tex]e=xy[/tex] is a bridge if and only if it lies on no cycle. If [tex]e[/tex] lies on a cycle [tex]C[/tex], every walk using [tex]e[/tex] can be rerouted along the path [tex]C-e[/tex], so removing [tex]e[/tex] disconnects nothing. Conversely, if [tex]e[/tex] is not a bridge, then [tex]x[/tex] and [tex]y[/tex] are joined by a path in [tex]G-e[/tex], and this path together with [tex]e[/tex] forms a cycle.
Fact [tex]2[/tex]: removing a bridge [tex]e=xy[/tex] increases the number of components by exactly [tex]1[/tex]. Indeed, only the component containing [tex]e[/tex] changes, and every vertex [tex]w[/tex] of it is joined to [tex]x[/tex] in [tex]G[/tex] by a path; cutting this path at its first use of [tex]e[/tex] (if any) gives a path in [tex]G-e[/tex] from [tex]w[/tex] to [tex]x[/tex] or to [tex]y[/tex]. So this component splits into at most two parts, and into exactly two, because [tex]e[/tex] is a bridge.
Now let [tex]B[/tex] be the set of bridges of [tex]G[/tex] and let [tex]H=G-B[/tex] (the same vertices, without the bridges).
Step [tex]1[/tex]: [tex]c(H)=c(G)+|B|[/tex]. Remove the bridges one at a time. Removing edges creates no new cycles, so by Fact [tex]1[/tex] every remaining edge of [tex]B[/tex] is still a bridge of the current graph, and by Fact [tex]2[/tex] each removal increases the number of components by exactly [tex]1[/tex].
Step [tex]2[/tex]: the components of [tex]H[/tex] are exactly the [tex]2[/tex]-edge-connected components of [tex]G[/tex].
Every component [tex]K[/tex] of [tex]H[/tex] is [tex]2[/tex]-edge-connected. Let [tex]e[/tex] be an edge of [tex]K[/tex]. It is not a bridge, so by Fact [tex]1[/tex] it lies on a cycle [tex]C[/tex] of [tex]G[/tex]. No edge of [tex]C[/tex] is a bridge (each of them lies on [tex]C[/tex]), so [tex]C\subseteq H[/tex], and since [tex]C[/tex] is connected and contains [tex]e[/tex], we have [tex]C\subseteq K[/tex]. Replacing [tex]e[/tex] by the path [tex]C-e[/tex] in any walk in [tex]K[/tex] shows that [tex]K-e[/tex] is connected.
Every [tex]2[/tex]-edge-connected subgraph [tex]S[/tex] of [tex]G[/tex] lies in one component of [tex]H[/tex]. If [tex]S[/tex] contained a bridge [tex]e=xy[/tex], then [tex]S-e[/tex] would be connected, so [tex]x[/tex] and [tex]y[/tex] would be connected in [tex]G-e[/tex] and [tex]e[/tex] would lie on a cycle, contradicting Fact [tex]1[/tex]. Thus [tex]S\subseteq H[/tex], and being connected, [tex]S[/tex] lies in one component of [tex]H[/tex].
By these two statements, every component of [tex]H[/tex] is a maximal [tex]2[/tex]-edge-connected subgraph of [tex]G[/tex], and every maximal [tex]2[/tex]-edge-connected subgraph is contained in a component of [tex]H[/tex], hence equal to it (isolated vertices of [tex]H[/tex] are one-vertex components). Therefore
[tex]c_2(G)=c(H)=c(G)+|B|\ \Rightarrow\ |\mathrm{br}(G)|=c_2(G)-c(G)[/tex]

Solution:
Let [tex]n=10[/tex], [tex]m=26[/tex], let [tex]t[/tex] be the number of triangles, [tex]d(v)[/tex] the degree of a vertex [tex]v[/tex] and [tex]N(v)[/tex] the set of its neighbours. The triangles containing an edge [tex]xy[/tex] are [tex]xyz[/tex] with [tex]z\in N(x)\cap N(y)[/tex], and every triangle has [tex]3[/tex] edges, so
[tex]3t=\sum_{xy\in E}|N(x)\cap N(y)|[/tex]
Since [tex]N(x)\cup N(y)\subseteq V[/tex], by inclusion-exclusion
[tex]|N(x)\cap N(y)|=d(x)+d(y)-|N(x)\cup N(y)|\ge d(x)+d(y)-n[/tex]
Summing over all edges, we get [tex]3t\ge\sum_{xy\in E}\left(d(x)+d(y)\right)-mn[/tex]. In this sum every vertex [tex]v[/tex] occurs in [tex]d(v)[/tex] edges and contributes [tex]d(v)[/tex] each time, so the sum equals [tex]\sum_{v\in V}d(v)^2[/tex]. By the Cauchy-Schwarz inequality and the handshake lemma
[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]
Therefore
[tex]3t\ge\frac{4m^2}{n}-mn=\frac{4\times 676}{10}-260=270.4-260=10.4[/tex]
so [tex]t\ge\frac{10.4}{3}\gt 3[/tex]. Since [tex]t[/tex] is an integer, [tex]t\ge 4[/tex].

Solution:
Consider the graph whose vertices are the people and whose edges are the friendships: any two distinct vertices have exactly one common neighbour. Let [tex]n[/tex] be the number of vertices; for [tex]n=1[/tex] the claim is true, so let [tex]n\ge 2[/tex].
Step [tex]1[/tex]: every degree is even. Let [tex]v[/tex] be a vertex and [tex]u\in N(v)[/tex], where [tex]N(v)[/tex] is the set of neighbours of [tex]v[/tex]. The pair [tex]u,v[/tex] has exactly one common neighbour [tex]u'[/tex]; it belongs to [tex]N(v)[/tex], and [tex]u'\ne u[/tex]. The common neighbour of [tex]u'[/tex] and [tex]v[/tex] is [tex]u[/tex], so the map [tex]u\mapsto u'[/tex] is an involution of [tex]N(v)[/tex] without fixed points. It splits [tex]N(v)[/tex] into pairs [tex]\{u,u'\}[/tex], hence the degree [tex]d(v)=|N(v)|[/tex] is even.
Step [tex]2[/tex]: fix a vertex [tex]v[/tex] and let [tex]W=V\setminus\left(N(v)\cup\{v\}\right)[/tex], so [tex]|W|=n-1-d(v)[/tex]. A vertex [tex]u\in N(v)[/tex] is adjacent to [tex]v[/tex], to [tex]u'[/tex] and to no other vertex of [tex]N(v)[/tex] (another one would be a second common neighbour of [tex]u[/tex] and [tex]v[/tex]), so [tex]u[/tex] has exactly [tex]d(u)-2[/tex] neighbours in [tex]W[/tex]. Every [tex]w\in W[/tex] has exactly one common neighbour with [tex]v[/tex], i.e. exactly one neighbour in [tex]N(v)[/tex]. Counting the edges between [tex]N(v)[/tex] and [tex]W[/tex] in two ways, we get
[tex]n-1-d(v)=|W|=\sum_{u\in N(v)}\left(d(u)-2\right)[/tex]
By Step [tex]1[/tex] the right-hand side is even and [tex]d(v)[/tex] is even, so [tex]n-1[/tex] is even and [tex]n[/tex] is odd. (Example: [tex]k[/tex] triangles with one common vertex give such a group of [tex]2k+1[/tex] people.)

Solution:
Let [tex]H[/tex] be the “stranger” graph: two people are adjacent in [tex]H[/tex] if they do not know each other. Since everybody has the same number [tex]d[/tex] of acquaintances, [tex]H[/tex] is regular of degree [tex]s=n-1-d[/tex], and [tex]s\ge 1[/tex] because there are two strangers. The people who stay form a set [tex]S[/tex] with no edge of [tex]H[/tex] inside it (an independent set of [tex]H[/tex]).
Count the edges of [tex]H[/tex] between [tex]S[/tex] and [tex]V\setminus S[/tex]. Every vertex of [tex]S[/tex] has all its [tex]s[/tex] neighbours outside [tex]S[/tex], which gives exactly [tex]s|S|[/tex] edges; every vertex outside [tex]S[/tex] has at most [tex]s[/tex] neighbours in [tex]S[/tex], which gives at most [tex]s(n-|S|)[/tex] edges. Hence, since [tex]n[/tex] is odd,
[tex]s|S|\le s(n-|S|)\ \Rightarrow\ |S|\le\frac{n}{2}\ \Rightarrow\ |S|\le\frac{n-1}{2}[/tex]
Therefore in every such company at least [tex]n-\frac{n-1}{2}=\frac{n+1}{2}[/tex] people must leave.
Example where this is enough: the [tex]n[/tex] people sit at a round table and each of them knows everybody except his two neighbours at the table. Everybody has [tex]n-3[/tex] acquaintances, and there are people who do not know each other. The people in seats [tex]1,3,5,\ldots,n-2[/tex] (that is [tex]\frac{n-1}{2}[/tex] people, no two of them neighbours) all know each other, so it suffices that the other [tex]\frac{n+1}{2}[/tex] people leave. Hence
[tex]k=\frac{n+1}{2}[/tex]