Graph Completeness and Subgraph Classification

00:00 6 marks

Consider a graph \(G\) with 6 vertices. In graph \(G\), all possible edges are present, making it complete, while in graph \(H\) with 6 vertices, exactly one edge is missing.

(a) Determine whether graph \(G\) is complete and whether graph \(H\) is complete. Justify your answer using the formula for the number of edges in a complete graph.

(b) For graph \(H\), identify a subgraph that is complete and describe the process of selecting this subgraph based on the vertex-edge relationship.

Part a

5 minutes 3 marks

Question

Determine whether graph \(G\) (with 15 edges) is complete and whether graph \(H\) (with 14 edges) is complete. Justify your answer using the formula \(\frac{n(n-1)}{2}\) for the number of edges in a complete graph.

Hint Hint

Hint

Compute \(\frac{6 \times 5}{2}\) and compare it with the given number of edges in each graph.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

Graph \(G\) is complete since it has 15 edges, which is equal to \(\frac{6 \times 5}{2}\), while graph \(H\) is not complete as it has only 14 edges.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet

Part b

5 minutes 3 marks

Question

For graph \(H\), identify a complete subgraph. Describe your process for selecting this subgraph using vertex-edge relationships.

Hint Hint

Hint

Consider removing a vertex that is connected to the missing edge in \(H\) to form a complete subgraph on 5 vertices.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

By removing one vertex that is incident to the missing edge in graph \(H\), the remaining subgraph is a complete graph \(K_5\) with \(\frac{5 \times 4}{2} = 10\) edges.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet