Four Extremal Words, Two Different Questions
In graph proofs, an object can be optimal in size without containing every other feasible object, and it can be impossible to enlarge without being largest. Similar distinctions apply when we try to shrink an object or choose a counterexample. The words maximum and minimum compare an object with the whole feasible family; maximal and minimal ask whether a strict enlargement or reduction remains feasible. The relevant order and the quantity being optimized must be stated.
Let \(\mathcal{F}\) be a family of objects with a partial order \(\preceq\). A partial order is a relation that is reflexive, antisymmetric and transitive. Write \(x\prec y\) when \(x\preceq y\) and \(x\ne y\). For vertex sets or edge sets, the usual order is inclusion. For graphs, it is usually the subgraph relation: \(H\) is a subgraph of \(G\) if \(V(H)\subseteq V(G)\) and every edge of \(H\) is an edge of \(G\) with both endpoints in \(V(H)\).
A maximum element, if it exists, is unique: if \(x\) and \(z\) are both maximum, then \(x\preceq z\) and \(z\preceq x\), so antisymmetry gives \(x=z\). A family can have several maximal elements, none of which is maximum. The same contrast holds between minimum and minimal. For a family of sets ordered by inclusion, “maximal” means no feasible strict superset, while “maximum” in the order-theoretic sense means a feasible set containing every feasible set.
Graph theory also commonly uses “maximum” to mean largest cardinality. For example, a maximum matching is a matching with as many edges as any matching. This is an optimization of a numerical objective, not necessarily a greatest matching under inclusion. A maximal matching is instead one to which no edge can be added while retaining a matching. Always identify whether the comparison is by inclusion, cardinality, order, size, or another stated quantity.
Why Maximal Does Not Mean Largest
Proof. Suppose \(x\) is maximum. If some \(y\) satisfied \(x\prec y\), then the definition of maximum would give \(y\preceq x\). Together with \(x\preceq y\), antisymmetry would imply \(x=y\), contradicting \(x\prec y\). Thus \(x\) is maximal. Reversing the order proves that every minimum element is minimal. The converses can fail because an element may have no feasible strict extension while another incomparable element is larger in the objective of interest. The examples below exhibit this failure for graph families. \(\square\)
Worked Example: A Maximal Matching That Is Not Maximum
Let \(G=(V,E)\) be the simple graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). A matching is a set of edges no two of which share an endpoint. Compare \(M=\{23\}\) with \(M'=\{12,34\}\).
The only edges of \(G\) are \(12,23,34\). Neither \(12\) nor \(34\) can be added to \(M\), because each shares an endpoint with \(23\). Thus \(M\) is maximal under edge-set inclusion, and its size is \(|M|=1\). The edges \(12\) and \(34\) have disjoint endpoints, so \(M'\) is a matching with \(|M'|=2\).
There cannot be a matching of size greater than \(2\): every matching edge uses two distinct vertices, and \(G\) has only four vertices. Therefore the maximum matching size is \(\nu(G)=2\), and \(M'\) is maximum. In particular, \(M\) is maximal but not maximum.
Check: \(M'\) uses all four vertices exactly once, while \(M\) uses vertices \(2\) and \(3\); each asserted matching has no shared endpoints among its edges. This verifies the feasibility and the sizes directly.
The inclusion order explains the distinction. The matching \(M\) cannot be enlarged by adding an edge, but it is not a largest matching by cardinality. A maximality check is local: it tests possible one-object extensions. A maximum claim requires comparison with every feasible object, or a separate argument bounding their sizes.
Vertex Sets: Independent Sets and Covers
A vertex set is independent if no two of its vertices are adjacent. A vertex cover is a set of vertices containing at least one endpoint of every edge. A maximum independent set has largest cardinality among independent sets; its size is the independence number \(\alpha(G)\). A maximal independent set has no strict independent superset. A minimum vertex cover has smallest cardinality; its size is \(\tau(G)\). A minimal vertex cover has no proper subset that is still a vertex cover. These are different optimization directions: adding vertices preserves being a cover, while removing vertices may destroy it.
Worked Example: Maximal and Maximum Independent Sets
Let \(G=(V,E)\) have \(V=\{c,a,b,d\}\) and \(E=\{ca,cb,cd\}\), the star with centre \(c\) and three leaves. Consider \(I_1=\{c\}\) and \(I_2=\{a,b,d\}\).
The set \(I_1\) is independent because it has only one vertex. It is maximal: adding any of \(a,b,d\) creates an edge with \(c\). Its cardinality is \(|I_1|=1\). The set \(I_2\) is independent because there are no edges between leaves. Any independent set containing \(c\) contains no leaves and has size at most \(1\); any independent set not containing \(c\) is a subset of \(\{a,b,d\}\), so has size at most \(3\). Thus \(\alpha(G)=3\), attained by \(I_2\). It is also maximal, since the only vertex outside it is \(c\), which is adjacent to all three leaves.
Check: the two maximal independent sets displayed have sizes \(1\) and \(3\). The larger is maximum, while the smaller shows that maximality alone does not establish maximum cardinality.
Worked Example: Minimal and Minimum Vertex Covers
Use the same graph \(V=\{c,a,b,d\}\), \(E=\{ca,cb,cd\}\). Compare \(C_1=\{c\}\) and \(C_2=\{a,b,d\}\).
The set \(C_1\) covers all three edges, since each edge is incident with \(c\). The empty set does not cover any edge, so \(C_1\) has no proper subset that is a cover. Hence it is minimal. It is also minimum: the empty set fails, and the cover \(C_1\) has size \(1\), so \(\tau(G)=1\).
The set \(C_2\) also covers every edge: \(a\) covers \(ca\), \(b\) covers \(cb\), and \(d\) covers \(cd\). Removing any one leaf leaves its incident edge uncovered, so \(C_2\) is minimal. But its size is \(3\), greater than \(|C_1|=1\), so \(C_2\) is not minimum.
Check: every edge is covered by \(C_1\) and by \(C_2\); each singleton removal from \(C_2\) misses one of the three listed edges. These checks establish coverage and minimality without confusing them with minimum size.
Existence in Finite Families
Proof. Choose any \(x_0\) in the family. If \(x_0\) is not maximal, choose \(x_1\) with \(x_0\prec x_1\). Continue whenever the current element is not maximal. No element can repeat: a repeated element would, by transitivity, imply \(x_i\prec x_i\), which contradicts the definition of strict order. Since the family is finite, this sequence must stop, and the last element is maximal. Apply the same argument with the order reversed to obtain a minimal element. This argument does not produce a maximum: it only follows one sequence of strict increases and does not show that its endpoint is comparable with every element of the family. The two-element family of incomparable elements has maximal elements but no maximum, and likewise has minimal elements but no minimum. \(\square\)
The nonempty hypothesis matters: the empty family has no element that could be maximal or minimal. In graph applications, the feasible family is often nonempty because it contains the empty edge set, the empty vertex set, or a specified starting graph, but that should be checked for the particular problem.
Subgraphs and Counterexamples
When selecting a subgraph, first specify the property that makes it feasible and the order used to compare feasible subgraphs. “Inclusion-maximal subgraph with property \(P\)” means that no strictly larger subgraph of the given graph still has \(P\). “Maximum-order subgraph with property \(P\)” means one with the largest number of vertices among those subgraphs. “Maximum-size subgraph” instead optimizes the number of edges. Those are distinct questions unless an argument connects the quantities. If a subgraph is required to be spanning, its vertex set is fixed, so inclusion comparisons typically concern its edges.
For counterexamples, “minimum” often refers to the number of vertices or edges, whereas “minimal” often refers to the subgraph relation: a counterexample is subgraph-minimal if none of its proper subgraphs is a counterexample. A smallest-order counterexample need not be the only subgraph-minimal one. State both the family of counterexamples and the chosen comparison before using either word.
Worked Example: Minimum-Order and Subgraph-Minimal Counterexamples
Consider the assertion that every finite simple graph has neither a triangle nor a path on four vertices. A counterexample to this assertion is a graph containing a triangle or a \(P_4\) as a subgraph. Here \(P_4\) means a path with four distinct vertices and three successive edges.
The triangle \(K_3\), with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\), is a counterexample of order \(3\). No graph of order less than \(3\) can contain a triangle or a \(P_4\), so order \(3\) is the minimum possible counterexample order.
Now let \(H=P_4\), with \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,23,34\}\). It is a counterexample because it contains a \(P_4\). No proper subgraph of \(H\) contains a triangle, since \(H\) itself has no triangle; and no proper subgraph contains a \(P_4\), since such a path would require all four vertices and all three edges of \(H\). Thus \(H\) is subgraph-minimal among counterexamples. It is not minimum-order, because \(K_3\) is a smaller counterexample.
Check: \(K_3\) has three vertices, while \(P_4\) has four. The order comparison establishes that \(P_4\) is not minimum-order; the proper-subgraph check establishes that it is minimal under subgraph inclusion. The two claims use different comparisons.
A Reliable Test for Extremal Language
Before asserting that an object is extremal, write down the feasible family, the order or numerical objective, and the exact claim. For example, “\(M\) is a maximal matching” asks whether an edge can be added while preserving the matching property. “\(M\) is a maximum matching” asks whether any matching has more edges. One fact does not answer both questions.
A common incorrect calculation is: “In \(P_4\), \(M=\{23\}\) is maximal, so \(\nu(P_4)=|M|=1\).” The first clause is true, but the conclusion does not follow. The matching \(\{12,34\}\) has size \(2\), and no matching can use more than two edges on four vertices because each edge requires two distinct vertices. Therefore \(\nu(P_4)=2\), not \(1\). The correction is to test maximality by possible extensions, and to prove maximum size by comparing with all possibilities or establishing an upper bound.
The same discipline works for sets and subgraphs. To prove that a vertex set is maximal, rule out every feasible strict superset. To prove it is maximum by cardinality, give an upper bound on the size of every feasible set and show that the proposed set attains it. To prove a cover is minimal, check that deleting any part makes it fail to cover; to prove it is minimum, compare its size with every cover. Keep the extremal word tied to the comparison that the proof actually establishes.
Check Your Understanding
For each question, state the order or objective being used, then justify the conclusion.
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), is \(\{23\}\) a maximal matching, a maximum matching, both, or neither?
- For the star with centre \(c\) and leaves \(a,b,d\), compare \(\{c\}\) and \(\{a,b,d\}\) as independent sets. Which are maximal, and which is maximum?
- Explain why a maximum element in a partially ordered family must be maximal, but a maximal element need not be maximum.
- What must be checked to show that a vertex cover is minimal? What additional comparison is needed to show it is minimum?
- Distinguish a minimum-order counterexample from a subgraph-minimal counterexample.