Parameter Formulas for Disjoint Unions

Why Disjoint Components Simplify Parameter Calculations

When a graph consists of several parts with no edges between them, choices made in one part cannot create conflicts or coverage in another. This makes some graph parameters additive. Other parameters, such as the size of a largest clique, are controlled by just one part. The distinction is useful both for computing parameters and for checking whether a proposed calculation makes sense.

Throughout, graphs are finite and simple. If $G_1,\ldots,G_r$ have pairwise disjoint vertex sets, their disjoint union $G=G_1\cup\cdots\cup G_r$ has vertex set the union of their vertex sets and edge set the union of their edge sets; in particular, there are no edges between different $G_i$. Empty graphs are permitted. We use $\alpha(G)$ for the independence number, $\omega(G)$ for the clique number, $\tau(G)$ for the vertex-cover number, and $\nu(G)$ for the matching number.

Definition: An independent set contains no adjacent pair of vertices; $\alpha(G)$ is the largest size of such a set. A clique is a set of pairwise adjacent vertices; $\omega(G)$ is the largest clique size. A vertex cover is a set of vertices incident with every edge; $\tau(G)$ is the smallest size of one. A matching is a set of edges with no shared endpoints; $\nu(G)$ is the largest size of one. An edge cover is a set of edges incident with every vertex. Write $\rho(G)$ for the minimum size of an edge cover when one exists.

The empty graph on no vertices has $\alpha=\omega=\tau=\nu=0$, and its empty edge set is an edge cover, so $\rho=0$. If a graph has an isolated vertex, it has no edge cover: no edge can be incident with that vertex. This condition matters when applying a formula for $\rho$.

The Disjoint-Union Formulas

Theorem: Let $G=G_1\cup\cdots\cup G_r$, where $r\geq 1$ and the graphs have pairwise disjoint vertex sets and no edges between them. Then $$ \begin{aligned} \alpha(G)&=\sum_{i=1}^{r}\alpha(G_i),& \tau(G)&=\sum_{i=1}^{r}\tau(G_i),\\ \nu(G)&=\sum_{i=1}^{r}\nu(G_i),& \omega(G)&=\max_{1\leq i\leq r}\omega(G_i). \end{aligned} $$ If every $G_i$ has no isolated vertices, then $G$ has an edge cover and $$ \rho(G)=\sum_{i=1}^{r}\rho(G_i). $$ If any $G_i$ has an isolated vertex, then $G$ has no edge cover.

Proof. An independent set $S$ in $G$ restricts to an independent set $S\cap V(G_i)$ in each $G_i$. Therefore $|S|=\sum_i |S\cap V(G_i)|\leq\sum_i\alpha(G_i)$. For the reverse inequality, choose in each $G_i$ an independent set of size $\alpha(G_i)$. Their union is independent in $G$, because there are no edges between different graphs, and its size is $\sum_i\alpha(G_i)$. This proves the formula for $\alpha$.

A vertex cover $C$ of $G$ restricts to a vertex cover $C\cap V(G_i)$ in every $G_i$, since every edge of $G_i$ must be covered. Hence $|C|\geq\sum_i\tau(G_i)$. Conversely, the union of minimum vertex covers of the $G_i$ covers every edge of $G$, and its size is $\sum_i\tau(G_i)$. Thus $\tau(G)=\sum_i\tau(G_i)$.

A matching $M$ in $G$ consists only of edges within individual $G_i$, so its restriction to each $G_i$ is a matching and $|M|\leq\sum_i\nu(G_i)$. Taking a maximum matching in each $G_i$ and combining them gives a matching in $G$: edges chosen from different graphs cannot share endpoints. Its size is $\sum_i\nu(G_i)$, proving the formula for $\nu$.

Every clique with at least two vertices has all its vertices in a single $G_i$, because every pair of its vertices must be adjacent and there are no edges between different $G_i$. A one-vertex clique also lies in one $G_i$. Thus any clique in $G$ has size at most $\max_i\omega(G_i)$. A largest clique in a graph $G_i$ attaining that maximum is also a clique in $G$, proving the formula for $\omega$.

Finally, suppose every $G_i$ has no isolated vertices. A minimum edge cover of each $G_i$ exists, and the union of these covers covers every vertex of $G$. In the other direction, any edge cover of $G$ restricts to an edge cover of each $G_i$, since every edge incident with a vertex of $G_i$ lies in $G_i$. Consequently its size is at least $\sum_i\rho(G_i)$, while the union of minimum covers has exactly that size. This proves the edge-cover formula. If some $G_i$ has an isolated vertex, that vertex is still isolated in $G$, so no edge cover exists. $\square$

The formulas reflect two different kinds of choices. Independent sets, vertex covers, and matchings can be selected separately in each component, so their optimum sizes add. A clique cannot draw vertices from multiple components, so its largest possible size is the largest component clique, not the sum. Edge covers also add, but only when every vertex can be incident with an edge.

Worked Calculations

Worked Example: A Path and an Edge

Let $G$ have $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,23,45\}$. Its components are the path on $1,2,3$ and the edge on $4,5$. Calculate all five parameters.

In the path component, $\{1,3\}$ is independent and no independent set can contain all three vertices because $12$ and $23$ are edges. Thus its independence number is $2$. In the edge component, an independent set has at most one endpoint, so its independence number is $1$. Therefore $\alpha(G)=2+1=3$; for example, $\{1,3,4\}$ attains this size.

The largest clique in the path component has size $2$, attained by either edge, and the largest clique in the edge component has size $2$. Hence $\omega(G)=\max(2,2)=2$. A vertex cover of the path component must cover both edges $12$ and $23$; vertex $2$ alone does so, giving cover number $1$. The edge component needs one endpoint in a cover, also giving $1$. Thus $\tau(G)=1+1=2$, attained by $\{2,4\}$.

The path component has matching number $1$, since its two edges share vertex $2$; the edge component has matching number $1$. Thus $\nu(G)=1+1=2$, attained by $\{12,45\}$. To cover the three vertices of the path component by edges, both $12$ and $23$ are needed; the edge component needs $45$. Therefore $\rho(G)=2+1=3$, attained by all three edges.

Check: The displayed independent set has size $3$, and $\{2,4\}$ covers $12,23,45$. The matching $\{12,45\}$ has two edges; it cannot be larger because each component contributes at most one. The edge cover has three edges, and its restriction to the path component must contain both edges to cover vertices $1$ and $3$. The computed clique size $2$ agrees with the fact that every edge is a two-vertex clique and no triangle occurs.

Worked Example: A Cycle and a Triangle

Let $G$ have $V(G)=\{1,2,3,4,a,b,c\}$ and $E(G)=\{12,23,34,41,ab,bc,ca\}$. The components are a 4-cycle on $1,2,3,4$ and a triangle on $a,b,c$.

For the 4-cycle, $\{1,3\}$ is independent, and no independent set can have three vertices: among any three vertices of the cycle, some two are adjacent. Its independence number is therefore $2$. The triangle has independence number $1$. Hence $\alpha(G)=2+1=3$, attained by $\{1,3,a\}$.

The 4-cycle has clique number $2$, while the triangle has clique number $3$, so $\omega(G)=\max(2,3)=3$. A vertex cover of the 4-cycle needs at least two vertices, since its two disjoint edges $12$ and $34$ require distinct cover vertices; $\{1,3\}$ is a cover of size $2$. A triangle needs at least two vertices to cover all three edges, and any two vertices do cover it. Thus $\tau(G)=2+2=4$.

The 4-cycle has a matching of size $2$, namely $\{12,34\}$, and no matching can use more than two edges on four vertices. In the triangle, any two edges share an endpoint, so its matching number is $1$. Therefore $\nu(G)=2+1=3$, attained by $\{12,34,ab\}$.

For an edge cover of the 4-cycle, $\{12,34\}$ covers all four vertices, and at least two edges are necessary because one edge is incident with only two vertices. The triangle has an edge cover of size $2$, for example $\{ab,bc\}$; one edge cannot cover all three vertices. Consequently $\rho(G)=2+2=4$.

Check: The graph has $7$ vertices. The independent set $\{1,3,a\}$ has size $3$, and its complement $\{2,4,b,c\}$ is the displayed vertex cover of size $4$. The three-edge matching uses six distinct vertices, and the component bounds $2$ and $1$ rule out a larger one. The four edges in the stated edge cover cover all seven vertices; no smaller cover is possible because the two components require at least two edges each.

Worked Example: An Isolated Vertex Prevents an Edge Cover

Let $G$ have $V(G)=\{a,b,c,d,e,f\}$ and $E(G)=\{ab,bc,ca,ef\}$. Its components are the triangle on $a,b,c$, the isolated vertex $d$, and the edge on $e,f$.

The triangle contributes independence number $1$, the isolated vertex contributes $1$, and the edge contributes $1$. Thus $\alpha(G)=1+1+1=3$, attained by $\{a,d,e\}$. The component clique numbers are $3,1,2$, respectively, so $\omega(G)=\max(3,1,2)=3$.

The triangle needs two vertices in a vertex cover, the isolated vertex needs none because it is incident with no edge, and the edge needs one endpoint. Therefore $\tau(G)=2+0+1=3$, attained by $\{a,b,e\}$. The triangle contributes matching number $1$, the isolated vertex contributes $0$, and the edge contributes $1$, giving $\nu(G)=1+0+1=2$, attained by $\{ab,ef\}$.

There is no edge cover of $G$: vertex $d$ is isolated, so no edge is incident with it. Thus $\rho(G)$ is not a finite number under the definition used here.

Check: The set $\{a,d,e\}$ contains no adjacent pair; $\{a,b,e\}$ covers $ab,bc,ca,ef$; and the two edges $ab,ef$ have no shared endpoint. The isolated vertex contributes to independence but not to vertex-cover size, and it prevents edge coverage entirely.

Repeated Components and a Common Mistake

Corollary: If $G$ is the disjoint union of $k\geq1$ copies of a graph $H$, then $\alpha(G)=k\alpha(H)$, $\tau(G)=k\tau(H)$, and $\nu(G)=k\nu(H)$, while $\omega(G)=\omega(H)$. If $H$ has no isolated vertices, then $\rho(G)=k\rho(H)$.

Proof. Apply the disjoint-union theorem to the $k$ component graphs, each of which has the same parameter values as $H$. The three additive formulas and the edge-cover formula give $k$ copies of the corresponding value. The maximum of $k$ identical clique numbers is $\omega(H)$. If $H$ has no isolated vertices, each copy has an edge cover, so the edge-cover formula applies. $\square$

A common error is to add clique numbers. For example, in the union of a triangle and a 4-cycle, the component clique numbers are $3$ and $2$. The incorrect calculation $3+2=5$ treats vertices from different components as if they were adjacent. In fact, a clique cannot contain vertices from both components, so the correct calculation is $\omega(G)=\max(3,2)=3$.

The edge-cover condition is another important check. Additivity does not turn a graph with an isolated vertex into one with an edge cover. Before calculating $\rho$, inspect every component for isolated vertices. If there is one, the edge-cover question is settled: no edge cover exists.

Check Your Understanding

Use component-by-component reasoning. State any edge-cover condition needed for your answer.

If $G$ is the disjoint union of three copies of $P_2$, find $\alpha(G)$, $\omega(G)$, $\tau(G)$, $\nu(G)$, and $\rho(G)$.
Explain why the clique number of a disjoint union is a maximum, while the independence number is a sum.
A graph is the disjoint union of $C_4$ and one isolated vertex. Does it have an edge cover? Find its independence number and matching number.
Prove directly from the definitions that the union of maximum matchings in the components is a matching in the whole graph.
Suppose two components have independence numbers $2$ and $4$, and clique numbers $3$ and $2$. Find the independence and clique numbers of their disjoint union.

Parameter Formulas for Disjoint Unions

What You'll Learn