From a Practical Question to a Graph
Many selection problems ask for a large group of objects with no pairwise conflict. Other problems ask for a small set of objects whose removal eliminates every conflict, or for a small set of services that reaches every required location. Graph parameters give concise models for these tasks. The important step is to decide what the vertices and edges represent: an edge may record a conflict, or it may represent a service that covers its two endpoints. Those interpretations lead to different graph problems.
All graphs in this tutorial are finite and simple: edges are undirected, with no loops or multiple edges. A set \(S\subseteq V(G)\) is an independent set if no two vertices in \(S\) are adjacent. A vertex cover is a set \(C\subseteq V(G)\) such that every edge has at least one endpoint in \(C\). Their largest and smallest possible sizes are the independence number \(\alpha(G)\) and the vertex cover number \(\tau(G)\).
This model is exact when feasibility is determined entirely by pairwise conflicts. It does not automatically encode restrictions such as a limit on the total cost, a requirement to choose exactly one object from each category, or a conflict involving three objects that does not arise from any conflicting pair. Such conditions need additional modeling, or a different mathematical structure.
Conflict Graphs: Selection and Removal
Suppose the goal is to select as many mutually compatible objects as possible. Put one vertex in the graph for each object, and draw an edge for each incompatible pair. An independent set contains no conflicting pair, so it represents a feasible selection. Conversely, every feasible selection is independent: if it contained both endpoints of an edge, it would include a conflicting pair.
The same graph models a related question: which objects should be removed so that no conflict remains among those retained? The removed vertices must touch every conflict edge, so they form a vertex cover. The following result makes the relationship precise.
Proof. Suppose \(S\) is independent. For any edge \(uv\in E\), its endpoints cannot both lie in \(S\). Therefore at least one endpoint lies in \(V\setminus S\), so \(V\setminus S\) is a vertex cover. Conversely, suppose \(V\setminus S\) is a vertex cover. If an edge had both endpoints in \(S\), it would have no endpoint in \(V\setminus S\), contradicting the definition of a vertex cover. Thus \(S\) is independent. Taking complements pairs every independent set of size \(k\) with a vertex cover of size \(|V|-k\). A largest independent set therefore corresponds to a smallest vertex cover, giving \(\alpha(G)=|V|-\tau(G)\), or equivalently \(\alpha(G)+\tau(G)=|V|\). This also holds when \(V=\varnothing\), since both parameters are then \(0\). \(\square\)
Worked Example: Choosing Compatible Volunteers
Five volunteers are labelled \(A,B,C,D,E\). The only incompatible pairs are \(AB, AC, BD, CE\). Model this by the graph \(G=(V,E)\) with \(V=\{A,B,C,D,E\}\) and \(E=\{AB,AC,BD,CE\}\). We seek a largest group with no pairwise conflict.
Consider \(S=\{A,D,E\}\). None of the four listed edges has both endpoints in \(S\): \(AB\) has endpoint \(B\) outside \(S\); \(AC\) has endpoint \(C\) outside \(S\); \(BD\) has endpoint \(B\) outside \(S\); and \(CE\) has endpoint \(C\) outside \(S\). Thus \(S\) is a feasible independent set of size \(3\).
To check that no larger group is possible, consider \(C_0=\{B,C\}\). The edge \(AB\) and the edge \(BD\) are incident with \(B\); the edge \(AC\) and the edge \(CE\) are incident with \(C\). Hence \(C_0\) is a vertex cover of size \(2\). Every independent set has a complementary vertex cover, so its size is at most \(5-2=3\). Therefore \(\alpha(G)=3\), and \(S\) is maximum.
Check: the selected volunteers are \(A,D,E\), and none of the pairs \(AD,AE,DE\) is an edge in \(E\). The cover \(C_0\) meets all four edges, while the independent set has size \(5-|C_0|=3\); the two certificates agree.
A vertex cover is useful when the practical question is framed as prevention rather than selection. If deleting a candidate removes all conflicts incident with it, a vertex cover is exactly a set of candidates whose removal leaves no conflict edge among the remaining candidates. A minimum vertex cover is one of smallest size; a merely inclusion-minimal cover need not be minimum. Likewise, a maximum independent set has largest size, not just the property that no single additional vertex can be added.
Worked Example: Removing the Fewest Conflicting Tasks
Four tasks \(p,q,r,s\) have conflicts \(pq,qr,rs,sp\), and there are no other conflicts. The conflict graph is \(G=(V,E)\), where \(V=\{p,q,r,s\}\) and \(E=\{pq,qr,rs,sp\}\). We want to remove as few tasks as possible so that the retained tasks have no conflicts.
The set \(C=\{p,r\}\) covers every edge: \(pq\) and \(sp\) meet \(p\), while \(qr\) and \(rs\) meet \(r\). Thus removing \(p\) and \(r\) works, using two removals. For a lower bound, the edges \(pq\) and \(rs\) have no common endpoint. Any vertex cover must choose at least one endpoint from \(pq\) and at least one endpoint from \(rs\); because these edges are disjoint, those choices must be two distinct vertices. So no cover of size \(0\) or \(1\) exists, and \(\tau(G)=2\).
The retained set is \(V\setminus C=\{q,s\}\). There is no edge \(qs\), so both tasks can be retained together. The complement proposition gives \(\alpha(G)=4-2=2\), confirming that this is also a largest compatible selection.
Check: the retained tasks \(q,s\) do not form any of the listed conflict pairs. The two disjoint conflict edges require at least two removals, and the proposed removal set uses exactly two.
Edge Covers: Covering Requirements with Edges
Sometimes the objects to be selected are services, links, or pairings, and the requirement is that every location or item be served by at least one selected object. When each available option serves exactly two requirements, represent each requirement by a vertex and each option by an edge joining the two requirements it serves. A set of selected options then covers every requirement exactly when the corresponding edges are incident with every vertex.
Thus edge covers and vertex covers reverse the roles of vertices and edges. A vertex cover selects vertices to meet every edge; an edge cover selects edges to meet every vertex. In the service interpretation, a requirement is met if at least one selected service includes it. The modeling is exact when every option covers precisely the two requirements at the endpoints of its edge.
Proof. If \(F\) is an edge cover, every vertex is incident with an edge of \(F\), so no vertex is isolated in \(G\). Conversely, suppose \(G\) has no isolated vertices. For each vertex \(v\), choose one edge \(e_v\) incident with \(v\), and let \(F\) be the set of all chosen edges. Every vertex is incident with its chosen edge, so \(F\) is an edge cover. If \(V=\varnothing\), there are no vertices to cover, and \(F=\varnothing\) satisfies the definition; the condition of having no isolated vertices holds vacuously. \(\square\)
Worked Example: Pairing Five Locations
Five locations \(a,b,c,d,e\) need service, and each available service connects two locations. The available connections are \(ab,bc,cd,de\). The graph is \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,cd,de\}\). We seek a smallest set of connections that reaches every location.
Choose \(F=\{ab,cd,de\}\). The edge \(ab\) covers \(a\) and \(b\); \(cd\) covers \(c\) and \(d\); and \(de\) covers \(d\) and \(e\). Together these edges are incident with all five vertices, so \(F\) is an edge cover of size \(3\).
For a lower bound, each selected edge has exactly two endpoints. A set of two edges can therefore be incident with at most four vertices, even if the edges have no endpoint in common. Since there are five vertices, every edge cover needs at least three edges. The displayed edge cover attains this bound, so \(\rho(G)=3\).
Check: \(a\) is incident with \(ab\), \(b\) with \(ab\), \(c\) with \(cd\), \(d\) with \(cd\) and \(de\), and \(e\) with \(de\). Two edges cannot cover five vertices because \(2\cdot 2=4<5\); the three-edge set is therefore minimum.
Some applications include an option that serves just one requirement. A simple way to represent such an option is to add a new private dummy vertex and an edge from the requirement to that dummy vertex. Since the dummy vertex has no other incident edge, every edge cover must select that edge, which enforces the singleton option’s coverage. If an option serves three or more requirements at once, an ordinary graph edge is not an exact representation: that situation calls for a model in which one selected object can cover more than two vertices.
Common Modeling Mistakes
Do not confuse what an edge means. In a conflict graph, selecting both endpoints of an edge is forbidden; the desired set is independent. In a coverage graph, selecting an edge is how its endpoints are served; the desired set is an edge cover. Treating every graph edge as a conflict regardless of the question can reverse the meaning of the model.
Do not confuse vertex covers and edge covers. In the five-location example, \(\{b,d\}\) is a vertex cover: every edge \(ab,bc,cd,de\) has endpoint \(b\) or \(d\). But it is not an edge cover, because it is a set of vertices, not edges. Even interpreting those labels as a mistaken selection would not serve locations \(a\) and \(e\). The edge cover \(\{ab,cd,de\}\) consists of edges and reaches every vertex.
Check the modeling assumptions. An independent set only enforces pairwise incompatibility. An edge cover only represents options that cover the two endpoints of their edges. Before optimizing a graph parameter, verify that vertices represent the required entities and that every edge has the intended meaning. A correct optimization on the wrong graph does not solve the practical problem.
Check Your Understanding
For each question, identify what the vertices and edges represent before choosing a graph parameter.
- A set of applicants has pairwise scheduling conflicts. What graph parameter models the largest group that can attend together?
- In a conflict graph, explain why the complement of a vertex cover is an independent set.
- For a coverage graph, what does it mean for a selected set of edges to be an edge cover?
- Can a graph with an isolated vertex have an edge cover? Give the reason from the definition.
- An available service covers three requirements at once. Why is a single ordinary graph edge not an exact representation of that option?