Graph Theory Fundamentals Questions and Answers

Answer: B

The statement that is always true is only II: at least one compound in \(U \setminus S\) reacts with an odd number of compounds.

Model the compounds as vertices of a graph, with an edge for each reacting pair. The handshaking lemma says the degrees add up to twice the number of edges, an even number.

The 9 compounds in \(S\) contribute \(9 \times 3 = 27\), which is odd. So the 14 compounds in \(U \setminus S\) must contribute an odd total, and a sum of integers is odd only if at least one of them is odd.

Statement I can fail (only one compound of \(U \setminus S\) needs odd degree), and III always fails, since if every degree in \(U \setminus S\) were even, the total would be odd.

Answer: B

The statement that is always true is \(G\) is a perfect matching.

A symmetric matrix that is its own inverse satisfies \(A^{2} = I\). For an adjacency matrix, the diagonal entry \((A^{2})_{ii}\) is the degree of vertex i, so every vertex has degree exactly 1. An off-diagonal entry \((A^{2})_{ij}\) counts paths of length 2 from i to j, and these are 0 automatically when every degree is 1. A graph in which every vertex has exactly one edge is a perfect matching.

A cycle has every degree 2, and a complete graph on more than two vertices has degree \(n - 1 \gt 1\), so neither works (except the single edge \(K_2\), which is itself a matching). Since a perfect matching does satisfy \(A^{2} = I\), such graphs exist.

Answer: D

The number of 3-cycles is the trace of \(A^{3}\) divided by 6.

The entry \((A^{3})_{ii}\) counts the closed walks of length 3 that start and end at vertex \(i\). In a simple graph a closed walk of length 3 must go round a triangle, since there are no loops or repeated edges to use.

Each triangle is counted several times in the trace: it can be started at any of its 3 vertices and traversed in either of 2 directions, giving \(3 \times 2 = 6\) closed walks. So the number of triangles is \(\frac{tr(A^{3})}{6}\).

The trace itself counts every triangle six times; dividing by 2 corrects only for direction and dividing by 3 only for the starting vertex.

Answer: A

The property that holds is The diagonal entries of \(A^{2}\) are the degrees of the vertices of the graph.

\((A^{2})_{ii} = \sum_{j} a_{ij} a_{ji} = \sum_{j} a_{ij}^{2} = \sum_{j} a_{ij}\), since \(A\) is symmetric with entries 0 or 1. That sum counts the neighbours of vertex \(i\), which is its degree.

The others fail. For the path on three vertices u - v - w (\(n = 3\)), the graph is connected, but \(A^{2} + I_{3}\) has a 0 in position (u, v): there is no walk of length exactly 2 from u to v, because the graph is bipartite. A triangle plus one isolated vertex has \(n = 4\) and its entries sum to \(6 = 2(n-1)\), yet it has a cycle. Two disjoint edges on four vertices put a 1 in every row and column, but the graph is not connected.

Answer: A

The graph has 5 faces.

Euler's formula holds for every connected planar graph:

\[ \begin{aligned} V - E + F &= 2 \\ 5 - 8 + F &= 2 \\ F &= 5 \end{aligned} \]

The count includes the unbounded outer face. 3 is just E - V, which leaves the 2 out of the formula, and 6 and 7 do not satisfy it for these values.

Answer: C

The false statement is G cannot be planar for any value of V and E.

The complete graphs \(K_{1}\) to \(K_{4}\) are all planar: \(K_{4}\) can be drawn as a triangle with a vertex in the middle joined to the three corners, with no edges crossing. Only from \(K_{5}\) onwards is a complete graph non-planar, by Kuratowski's theorem, so the statement fails for small V.

The other statements are true. A complete graph on V vertices needs exactly V colours, since every vertex is adjacent to every other, so it is V-colourable. Each pair of vertices is joined by one edge, giving \(E = V(V-1)/2\). And every vertex is adjacent to every other, so the graph is always connected.