Discrete Mathematics and Graph Theory: Problems with Solutions

Solution:
In a simple graph (no loops and no multiple edges) every vertex can be adjacent only to the other [tex]n-1[/tex] vertices, so the degree of every vertex belongs to the set [tex]\{0, 1, \ldots, n-1\}[/tex], which has [tex]n[/tex] elements.
The values [tex]0[/tex] and [tex]n-1[/tex] cannot both occur: a vertex of degree [tex]n-1[/tex] is adjacent to all other vertices, and then no vertex has degree [tex]0[/tex]. Hence the [tex]n[/tex] degrees take at most [tex]n-1[/tex] different values, from one of the sets
[tex]\{0, 1, \ldots, n-2\}\text{ or }\{1, 2, \ldots, n-1\}[/tex]
By the pigeonhole principle, two of the [tex]n[/tex] vertices have equal degrees.

Solution:
We use [tex]\overline{u}=u\oplus 1[/tex] and [tex]1\oplus 1=0[/tex]. First we substitute the negated variables:
[tex]f(\overline{x},\overline{y})=(x\oplus 1)\oplus(y\oplus 1)\oplus 1=x\oplus y\oplus 1[/tex]
Then we negate the result:
[tex]f^*(x,y)=\overline{x\oplus y\oplus 1}=x\oplus y\oplus 1\oplus 1=x\oplus y[/tex]
Check with the truth table: for [tex](x, y)[/tex] equal to [tex](0, 0)[/tex], [tex](0, 1)[/tex], [tex](1, 0)[/tex], [tex](1, 1)[/tex] the function [tex]f[/tex] takes the values [tex]1, 0, 0, 1[/tex], while [tex]f^*[/tex] takes the values [tex]0, 1, 1, 0[/tex], i.e. [tex]f^*=\overline{f}[/tex].
A common mistake is to compute only [tex]f(\overline{x},\overline{y})[/tex] and forget the outer negation; this gives [tex]f[/tex] itself, i.e. the wrong answer [tex]x\oplus y\oplus 1[/tex].

Solution:
Let [tex]A[/tex] be the adjacency matrix of [tex]G[/tex]. The entry [tex](A^k)_{ij}[/tex] equals the number of walks of length [tex]k[/tex] from [tex]v_i[/tex] to [tex]v_j[/tex] (by induction on [tex]k[/tex]: a walk of length [tex]k+1[/tex] is a walk of length [tex]k[/tex] followed by one more edge). In particular, [tex](A^2)_{ij}[/tex] is the number of common neighbors of [tex]v_i[/tex] and [tex]v_j[/tex] (the degree of [tex]v_i[/tex] when [tex]i=j[/tex]). The sets of neighbors of the vertices are:
[tex]N(v_1)=\{v_3,v_4,v_5\}, \quad N(v_2)=\{v_4,v_5\}, \quad N(v_3)=\{v_1,v_5\}[/tex]
[tex]N(v_4)=\{v_1,v_2,v_5\}, \quad N(v_5)=\{v_1,v_2,v_3,v_4\}[/tex]
Row [tex]2[/tex] of [tex]A^2[/tex] (common neighbors of [tex]v_2[/tex] with [tex]v_1,\ldots,v_5[/tex]) is [tex](2, 2, 1, 1, 1)[/tex], and column [tex]5[/tex] (common neighbors of [tex]v_5[/tex] with [tex]v_1,\ldots,v_5[/tex]) is [tex](2, 1, 1, 2, 4)[/tex]. Since [tex]A^4=A^2A^2[/tex], we get
[tex](A^4)_{25}=\sum_{k=1}^{5}(A^2)_{2k}(A^2)_{k5}=2\times 2+2\times 1+1\times 1+1\times 2+1\times 4=13[/tex]

Solution:
This is a linear nonhomogeneous recurrence relation with constant coefficients. Its characteristic equation [tex]r^2-3r+2=0[/tex] has roots [tex]r_1=1[/tex] and [tex]r_2=2[/tex], so the general solution of the homogeneous relation is [tex]C_1+C_2\times 2^n[/tex].
The right-hand side is the constant [tex]1=1\times 1^n[/tex], and [tex]1[/tex] is a simple root of the characteristic equation, so we look for a particular solution of the form [tex]p_n=Cn[/tex] (a constant would be absorbed by the homogeneous part):
[tex]Cn=3C(n-1)-2C(n-2)+1=Cn+C+1\Rightarrow C=-1[/tex]
Hence [tex]a_n=C_1+C_2\times 2^n-n[/tex]. From the initial conditions:
[tex]\begin{cases}C_1+2C_2-1=1\\ C_1+4C_2-2=2\end{cases}\Rightarrow C_2=1, \ C_1=0[/tex]
Therefore [tex]a_n=2^n-n[/tex]. Check:
[tex]a_3=3\times 2-2\times 1+1=5=2^3-3, \qquad a_4=3\times 5-2\times 2+1=12=2^4-4[/tex]

Solution:
Suppose that [tex]G[/tex] has no cycle. Let [tex]u[/tex] be the unique vertex of degree [tex]1[/tex] and let [tex]K[/tex] be the connected component of [tex]G[/tex] containing [tex]u[/tex]; it contains at least the edge joining [tex]u[/tex] to its neighbor. Since [tex]K[/tex] is finite, it has a longest path
[tex]P=w_0w_1\ldots w_k,\quad k\ge 1[/tex]
Let [tex]x[/tex] be a neighbor of [tex]w_0[/tex] different from [tex]w_1[/tex]. If [tex]x[/tex] lies on [tex]P[/tex], i.e. [tex]x=w_j[/tex] with [tex]j\ge 2[/tex], then [tex]w_0w_1\ldots w_jw_0[/tex] is a cycle. If [tex]x[/tex] does not lie on [tex]P[/tex], then [tex]xw_0w_1\ldots w_k[/tex] is a longer path. Both are impossible, so [tex]w_0[/tex] has no neighbors other than [tex]w_1[/tex] and its degree is [tex]d(w_0)=1[/tex]. In the same way [tex]d(w_k)=1[/tex].
Since [tex]k\ge 1[/tex], the vertices [tex]w_0[/tex] and [tex]w_k[/tex] are different, so [tex]G[/tex] has at least two vertices of degree [tex]1[/tex], which contradicts the hypothesis. Hence [tex]G[/tex] contains a cycle.