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.

Answer: B

The keyed answer is disjoint union of cycles, read as an edge-disjoint union.

Veblen's theorem: a graph in which every vertex has even degree has its edge set partitioned into edge-disjoint cycles. Start at any vertex and walk along unused edges; even degrees mean the walk can always leave a vertex it enters, so it closes into a cycle; remove it and repeat.

The cycles need not be vertex-disjoint: two triangles sharing one vertex (degrees 2, 2, 4, 2, 2) is such a graph. That same graph shows the other options fail: it contains odd cycles, so it is not bipartite; it has no cycle through all five vertices, so it is not Hamiltonian; and the shared vertex is a cut vertex.

Answer: D

The statement that is not true is G has at least two spanning trees.

A connected graph in which removing any edge disconnects it has no cycle (an edge on a cycle could be removed without disconnecting), so G is a tree. Then:

• G has no circuit (true).
• There is a unique path between any two vertices (true for trees).
• A tree with at least 2 vertices has at least two pendant vertices (true).

But a spanning tree of a tree must use all of its \(n - 1\) edges, so the only spanning tree of G is G itself. G has exactly one spanning tree, not two.

Answer: C

The answer is \(k = k'\) whenever G is 3-regular.

Whitney's inequality says \(k \le k' \le \delta\) for every graph. For a cubic (3-regular) graph the vertex and edge connectivity are always equal: a minimum vertex cut can be turned into an edge cut of the same size because each vertex has only three edges.

The other options contradict Whitney's inequality: \(\delta \le k'\) and \(k' \le k\) reverse it (they hold only in the equality case). And \(\delta = k'\) can fail for regular graphs: two copies of \(K_{5}\) with one edge removed from each, joined by two edges, form a 4-regular graph with edge connectivity 2.

Answer: B

The incidence matrix is 9×18.

A node (vertex)-edge incidence matrix has one row for each vertex and one column for each edge; entry (i, j) is 1 when vertex i is an end of edge j. The graph has 9 vertices (A to I) and 18 edges (e1 to e18), so the matrix is 9 rows by 18 columns. Each column holds exactly two 1s, because every edge of an undirected graph has two ends.

18×9 is the transpose, an edge-vertex arrangement. 9×9 is the size of the adjacency matrix, and 18×18 matches nothing. The weight set W does not affect the order of the matrix.