Graph Theory

By Cayley’s formula, the complete graph on \(n\) labelled vertices has \(n^{n-2}\) spanning trees, so \(K_{4}\) has \(4^{4-2} = 16\).

A direct count agrees. A spanning tree on 4 vertices has 3 edges, and \(K_{4}\) has 6 edges, so there are \(\binom{6}{3} = 20\) sets of 3 edges. Three edges on four vertices fail to form a tree only when they make a triangle (leaving the fourth vertex isolated), and \(K_{4}\) has 4 triangles: \(20 - 4 = 16\). They are the 12 paths and the 4 stars on A, B, C, D.

Answer: 16

Take a proper colouring with exactly \(k\) colours. Its colour classes are independent sets that split the \(n\) vertices into \(k\) groups.

• (B) True: the largest of the \(k\) classes has at least \(n/k\) vertices.
• (C) True: every two colour classes must be joined by at least one edge, otherwise they could share a colour and \(k - 1\) colours would do. That gives at least \(\binom{k}{2} = k(k - 1)/2\) edges.
• (A) False: the 5-cycle needs 3 colours but contains no triangle.
• (D) False: the complete graph \(K_{k}\) has chromatic number \(k\), yet every vertex has degree \(k - 1\).

Answer: B, C

\(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

(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