Discrete Mathematics and Graph Theory: Difficult Problems with Solutions

Solution:
For every [tex]n\ge 0[/tex] we have [tex]\binom{n}{3}=\frac{n(n-1)(n-2)}{6}[/tex] (for [tex]n=0, 1, 2[/tex] both sides are [tex]0[/tex]), so
[tex]f(n)=q(n)\,(-1)^n,\qquad q(n)=\frac{n(n-1)(n-2)}{6}[/tex]
where [tex]q[/tex] is a polynomial of degree [tex]3[/tex]. The general solution of the recurrence relation with characteristic polynomial [tex](x+1)^4[/tex] is [tex](C_1+C_2n+C_3n^2+C_4n^3)(-1)^n[/tex], because [tex]-1[/tex] is a root of multiplicity [tex]4[/tex]. Hence [tex]f[/tex] satisfies the relation of order [tex]4[/tex] with characteristic polynomial
[tex](x+1)^4=x^4+4x^3+6x^2+4x+1[/tex]
that is, the relation
[tex]f(n)=-4f(n-1)-6f(n-2)-4f(n-3)-f(n-4)[/tex]
There is no such relation of order [tex]k\le 3[/tex]: for [tex]n=3[/tex] its right-hand side is a linear combination of some of the values [tex]f(0)[/tex], [tex]f(1)[/tex], [tex]f(2)[/tex], which are all [tex]0[/tex], while [tex]f(3)=-1\ne 0[/tex]. So the lowest possible order is [tex]4[/tex]. Check with [tex]f(3)=-1[/tex], [tex]f(4)=4[/tex], [tex]f(5)=-10[/tex]:
[tex]f(4)=-4f(3)=-4\times (-1)=4, \qquad f(5)=-4f(4)-6f(3)=-16+6=-10[/tex]

Solution:
Divide the recurrence by [tex](n+1)![/tex] and put [tex]b_n=\frac{a_n}{n!}[/tex]. Then [tex]b_1=0[/tex] and
[tex]b_{n+1}-b_n=\frac{(-1)^{n+1}}{(n+1)!},\quad n\ge 1[/tex]
Adding these equalities for the indices from [tex]1[/tex] to [tex]n-1[/tex] (the left-hand sides telescope), we get
[tex]b_n=b_1+\sum_{k=2}^{n}\frac{(-1)^k}{k!}=\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex]
because the terms for [tex]k=0[/tex] and [tex]k=1[/tex] give [tex]1-1=0=b_1[/tex] (for [tex]n=1[/tex] the sum from [tex]k=2[/tex] is empty). Multiplying by [tex]n![/tex], we obtain [tex]a_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}[/tex].
Check: the recurrence gives [tex]a_2=1[/tex], [tex]a_3=2[/tex], [tex]a_4=9[/tex], and the formula gives
[tex]2!\left(1-1+\frac{1}{2}\right)=1, \quad 3!\left(\frac{1}{2}-\frac{1}{6}\right)=2, \quad 4!\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=9[/tex]

Solution:
Denote the Hamming distance by [tex]d[/tex]. The vectors [tex]\alpha[/tex] and [tex]\beta[/tex] differ in positions [tex]1[/tex], [tex]3[/tex], [tex]6[/tex], [tex]7[/tex] and agree in positions [tex]2[/tex], [tex]4[/tex], [tex]5[/tex], i.e. [tex]d(\alpha,\beta)=4[/tex].
In a position where [tex]\alpha[/tex] and [tex]\beta[/tex] agree, [tex]\gamma[/tex] adds the same amount ([tex]0[/tex] or [tex]1[/tex]) to [tex]d(\gamma,\alpha)[/tex] and to [tex]d(\gamma,\beta)[/tex]. So these [tex]3[/tex] positions do not affect the equality and [tex]\gamma[/tex] is arbitrary there: [tex]2^3=8[/tex] possibilities.
In each of the [tex]4[/tex] positions where they differ, [tex]\gamma[/tex] coincides with exactly one of [tex]\alpha[/tex] and [tex]\beta[/tex], so it adds [tex]1[/tex] to exactly one of the two distances. Hence [tex]d(\gamma,\alpha)=d(\gamma,\beta)[/tex] if and only if [tex]\gamma[/tex] coincides with [tex]\alpha[/tex] in exactly [tex]2[/tex] of these [tex]4[/tex] positions (and with [tex]\beta[/tex] in the other [tex]2[/tex]): [tex]\binom{4}{2}=6[/tex] possibilities.
By the product rule, the number of such vectors is
[tex]\binom{4}{2}\times 2^3=6\times 8=48[/tex]

Solution:
Let [tex]G[/tex] be such a graph and suppose that some vertex [tex]v[/tex] has degree at least [tex]3[/tex] in [tex]G[/tex]; let [tex]a,b,c[/tex] be three of its neighbours. If two of them are adjacent in [tex]G[/tex], they form a triangle with [tex]v[/tex] in [tex]G[/tex]; otherwise [tex]a,b,c[/tex] form a triangle in [tex]\overline{G}[/tex]. Hence every degree in [tex]G[/tex] is at most [tex]2[/tex].
The condition is symmetric in [tex]G[/tex] and [tex]\overline{G}[/tex], so every degree in [tex]\overline{G}[/tex] is also at most [tex]2[/tex]. Every vertex has [tex]4[/tex] possible neighbours, hence
[tex]d_G(v)=4-d_{\overline{G}}(v)\ge 4-2=2[/tex]
So every degree in [tex]G[/tex] equals [tex]2[/tex], i.e. [tex]G[/tex] is a disjoint union of cycles, each of length at least [tex]3[/tex], with [tex]5[/tex] vertices in total. Since [tex]5[/tex] is not a sum of two or more numbers [tex]\ge 3[/tex], the graph [tex]G[/tex] is a single cycle of length [tex]5[/tex].
Conversely, a cycle of length [tex]5[/tex] contains no triangle, and its complement is again a cycle of length [tex]5[/tex] (every vertex is joined to its two non-neighbours, which gives a pentagram), so it contains no triangle either.
It remains to count the cycles of length [tex]5[/tex] on [tex]5[/tex] labelled vertices. Each of the [tex]5![/tex] orderings of the vertices gives a cycle, and each cycle is obtained [tex]5\times 2[/tex] times ([tex]5[/tex] starting vertices and [tex]2[/tex] directions):
[tex]\frac{5!}{5\times 2}=\frac{120}{10}=12[/tex]

Solution:
Let [tex]n=|V|[/tex]. First we show that [tex]|E|\lt 3n[/tex]. For [tex]n\le 2[/tex] this is clear, since [tex]|E|\le 1[/tex]. Let [tex]n\ge 3[/tex]. Adding an edge between two components of a plane drawing keeps it planar and only increases [tex]|E|[/tex], so we may assume that [tex]G[/tex] is connected. Then the boundary walk of every face has length at least [tex]3[/tex], and every edge is counted at most twice in these walks. Together with Euler's formula [tex]n-|E|+F=2[/tex], where [tex]F[/tex] is the number of faces, this gives
[tex]3F\le 2|E|\ \Rightarrow\ 3(2-n+|E|)\le 2|E|\ \Rightarrow\ |E|\le 3n-6\lt 3n[/tex]
By the handshake lemma
[tex]\sum_{v\in V}d(v)=2|E|\lt 6n[/tex]
Let [tex]D=\frac{600}{100-p}\gt 0[/tex] and let [tex]q[/tex] be the number of vertices with [tex]d(v)\ge D[/tex]. Each of them contributes at least [tex]D[/tex] to the sum of the degrees, so
[tex]qD\le\sum_{v\in V}d(v)\lt 6n\ \Rightarrow\ q\lt\frac{6n}{D}=\frac{6n(100-p)}{600}=\frac{(100-p)n}{100}[/tex]
Consequently, the number of vertices of degree less than [tex]D[/tex] is
[tex]n-q\gt n-\frac{(100-p)n}{100}=\frac{pn}{100}[/tex]
i.e. more than [tex]p\%[/tex] of all vertices. This proves the statement.

Solution:
Nobody shakes hands with himself or with his partner, so each answer is one of the numbers from [tex]0[/tex] to [tex]8[/tex]. The [tex]9[/tex] answers are different, hence they are exactly
[tex]0,1,2,\ldots,8[/tex]
Call the person who answered [tex]j[/tex] “person [tex]j[/tex]”. Person [tex]8[/tex] shook hands with everybody except his or her partner. Person [tex]0[/tex] shook hands with nobody, in particular not with person [tex]8[/tex], so person [tex]0[/tex] is the partner of person [tex]8[/tex]. Both of them were asked, so neither of them is Mrs. Ivanova; and person [tex]8[/tex] is not Mr. Ivanov, because his partner, Mrs. Ivanova, was not asked. Hence persons [tex]8[/tex] and [tex]0[/tex] form one of the guest couples.
Remove this couple. Every remaining person shook hands with person [tex]8[/tex] and not with person [tex]0[/tex], so every remaining count decreases by exactly [tex]1[/tex]. We get the same situation with [tex]3[/tex] guest couples: the [tex]7[/tex] people asked now have the different counts [tex]0,1,\ldots,6[/tex].
Repeating the argument, persons [tex]7[/tex] and [tex]1[/tex], then [tex]6[/tex] and [tex]2[/tex], then [tex]5[/tex] and [tex]3[/tex] form guest couples, and the last person asked, person [tex]4[/tex], is Mr. Ivanov. At each step the person with the largest count shook hands with everybody present except the partner, in particular with Mrs. Ivanova, while the person with count [tex]0[/tex] did not shake hands with her. Mrs. Ivanova did not shake hands with her husband either. Hence she shook hands exactly with persons [tex]8[/tex], [tex]7[/tex], [tex]6[/tex] and [tex]5[/tex], i.e. with [tex]4[/tex] people.