AMU 2026 — Computer PYQ

To correctly fill in the blanks, we must look closely at the standard theoretical computer science definitions for both Clique and Vertex Cover in a graph $G=(V,E)$.

1. Understanding Clique:

   • A complete subgraph is a subset of vertices where every pair of distinct vertices is connected by an edge.

   • A Clique is formally defined as a maximal complete subgraph.

   • "Maximal" means you cannot add any more vertices from the graph to this subgraph without losing its property of being completely connected.

2. Understanding Vertex Cover:

   • A vertex cover of a graph is a subset of vertices such that each edge of the graph is incident to at least one vertex in the subset (the vertices "cover" all the edges).

   • A structural Vertex Cover optimization property focuses on finding a minimal subset of vertices.

   • "Minimal" means that if you remove even a single vertex from this subset, it will no longer remain a valid vertex cover because some edges will be left uncovered.

3. Matching the Order:

   • First blank (Clique) $\to$ maximal

   • Second blank (Vertex Cover) $\to$ minimal

Conclusion:

Combining both definitions sequentially yields maximal, minimal, which corresponds to option (a).