Discrete Mathematics

The characteristic equation is \(r^{2} - 5r + 6 = 0\), with roots 2 and 3, so \(T(n) = a \cdot 2^{n} + b \cdot 3^{n}\).

The initial values fix the constants: \(a + b = 1\) and \(2a + 3b = 2\), giving \(a = 1\) and \(b = 0\). Hence \(T(n) = 2^{n}\) exactly; for instance, \(T(2) = 5 \cdot 2 - 6 \cdot 1 = 4\).

These starting values make the \(3^{n}\) term vanish, so option C, which follows the larger root, is wrong here. Forms like \(n2^{n}\) and \(n3^{n}\) arise only from a repeated root.

Answer: A

\(A\) is its own inverse exactly when \(A^{2} = I\). The entry \((A^{2})_{ij}\) counts the walks of length 2 from vertex \(i\) to vertex \(j\).

• The diagonal entry \((A^{2})_{ii}\) is the degree of \(i\), so \(A^{2} = I\) forces every vertex to have degree exactly 1.
• When every degree is 1, no two vertices share a neighbour, so the off-diagonal entries are 0, as required.

So \(G\) is a set of disjoint edges, that is, a perfect matching, and every perfect matching does satisfy \(A^{2} = I\). A cycle fails because its vertices have degree 2. A complete graph works only as \(K_{2}\), a single edge, so two disjoint edges already show that C is not always true. A single edge also rules out D.

Answer: B

A total order that contains \(P\) is a linear extension of \(P\): an arrangement of 1, 2, 3, 4 in which 1 comes before 2, 3 comes before 2, and 3 comes before 4. Only the minimal elements 1 and 3 can come first.

• First 1: among 2, 3, 4 the element 3 must lead, and 2 and 4 follow in either order: 1, 3, 2, 4 and 1, 3, 4, 2.
• First 3: the remaining 1, 2, 4 only need 1 before 2, which half of their \(3! = 6\) orders satisfy: 3, 1, 2, 4; 3, 1, 4, 2; 3, 4, 1, 2.

So \(2 + 3 = 5\) total orders contain \(P\).

Answer: 5

(D) holds. Suppose a cycle \(C\) has an even edge \(e\) and an odd edge \(f\). Extend the path \(C - f\) to a spanning tree \(T\); it contains \(e\) but not \(f\). Removing \(e\) splits \(T\) into two parts, and \(f\) must join them, because the rest of the cycle links the ends of \(e\). So \(T - e + f\) is another spanning tree whose weight differs from that of \(T\) by an odd amount, and both cannot be even.

The others fail. A triangle with weights 1, 1, 1 has every spanning tree of weight 2, yet its edges are odd, which rules out (A) and (C). A path with weights 1, 1, 2 is its own only spanning tree (weight 4) and mixes parities, which rules out (B).

Answer: D

Any graph with an edge needs at least 2 colours, and exactly 2 suffice when the graph is bipartite. Go round the octagon and colour the corners alternately red and blue; the eight sides are properly coloured because 8 is even.

Every other edge (the two verticals, the two horizontals and the four long diagonals) joins two corners that are three steps apart around the octagon. Three is odd, so each of them joins a red corner to a blue corner.

No edge joins two corners of the same colour, so the graph is bipartite (it is in fact \(K_{4,4}\)) and its chromatic number is 2.

Answer: 2

The product group works coordinate by coordinate, so \((x, y, z)\) is its own inverse exactly when \(2x \equiv 0 \pmod 2\), \(2y \equiv 0 \pmod 3\) and \(2z \equiv 0 \pmod 4\).

• In \(Z_2\): both 0 and 1 work (2 choices).
• In \(Z_3\): only 0 works, since \(2 \cdot 1 = 2\) and \(2 \cdot 2 = 4 \equiv 1\) (1 choice).
• In \(Z_4\): 0 and 2 work (2 choices).

So there are \(2 \times 1 \times 2 = 4\) such elements: \((0,0,0), (0,0,2), (1,0,0), (1,0,2)\). The identity \((0,0,0)\) counts, since it is its own inverse.

Answer: 4