Parameter Formulas for Graph Joins

The Join Operation

The join connects two graphs more strongly than a disjoint union does: it keeps each graph’s internal edges and adds every edge between the two vertex sets. Those added edges sharply constrain independent sets, while they allow cliques to combine across the two graphs. We will derive the resulting formulas for the independence number, clique number, and vertex-cover number.

Definition: Let $G=(V_G,E_G)$ and $H=(V_H,E_H)$ be finite simple graphs with disjoint vertex sets. Their join, denoted $G\vee H$, has vertex set $V_G\cup V_H$ and edge set $$ E(G\vee H)=E_G\cup E_H\cup\{uv:u\in V_G,\ v\in V_H\}. $$ Thus every vertex of $G$ is adjacent to every vertex of $H$. If the original vertex sets overlap, take disjoint relabelled copies before forming the join.

An independent set is a set of vertices containing no adjacent pair; its largest possible size is the independence number $\alpha(G)$. A clique is a set of pairwise adjacent vertices; its largest possible size is the clique number $\omega(G)$. A vertex cover is a set of vertices containing at least one endpoint of every edge; the smallest possible size is the vertex-cover number $\tau(G)$. For the graph with no vertices, take $\alpha=\omega=\tau=0$.

These parameters respond differently to the cross-edges. An independent set cannot contain vertices from both sides, because any such pair would be adjacent. By contrast, a clique can combine a clique from each side: all the cross-pairs are adjacent. The cover formula follows from the fact that a set is a vertex cover exactly when its complement is independent.

Formulas for a Join

Theorem: For finite simple graphs $G,H$ on disjoint vertex sets, $$ \alpha(G\vee H)=\max\{\alpha(G),\alpha(H)\},\qquad \omega(G\vee H)=\omega(G)+\omega(H), $$ and $$ \tau(G\vee H)=|V(G)|+|V(H)|-\max\{\alpha(G),\alpha(H)\} =\min\{|V(G)|+\tau(H),\ |V(H)|+\tau(G)\}. $$ These formulas include the case in which one or both graphs have no vertices.

Proof. First consider an independent set $I$ in $G\vee H$. If $I$ contained some $u\in V(G)$ and some $v\in V(H)$, then $uv$ would be an edge by the definition of the join. This contradicts independence. Therefore $I$ lies entirely in $V(G)$ or entirely in $V(H)$, with the empty set allowed in either side. In the first case, $I$ is independent in $G$, so $|I|\leq\alpha(G)$; in the second, $|I|\leq\alpha(H)$. Hence $|I|\leq\max\{\alpha(G),\alpha(H)\}$. A largest independent set of whichever component has the larger independence number remains independent in the join, because it uses only that component’s vertices. Thus equality holds.

Now let $Q$ be a clique in $G\vee H$. The sets $Q\cap V(G)$ and $Q\cap V(H)$ are cliques in their respective graphs, so $|Q\cap V(G)|\leq\omega(G)$ and $|Q\cap V(H)|\leq\omega(H)$. The sets partition $Q$, giving $|Q|\leq\omega(G)+\omega(H)$. Conversely, choose a largest clique in each component. Their union is a clique in the join: pairs within each chosen set are adjacent in its component, and pairs with one vertex from each set are adjacent by the join definition. It has size $\omega(G)+\omega(H)$, proving the clique formula.

For any finite graph $F$, a subset $C\subseteq V(F)$ is a vertex cover if and only if $V(F)\setminus C$ is independent. Indeed, if two vertices outside $C$ were adjacent, that edge would have no endpoint in the cover. Conversely, if the complement is independent, no edge can have both endpoints outside $C$, so every edge meets $C$. Taking the smallest cover, or equivalently the largest independent complement, gives $\tau(F)=|V(F)|-\alpha(F)$. Apply this identity to $F=G\vee H$ and use the independence formula to obtain $\tau(G\vee H)=|V(G)|+|V(H)|-\max\{\alpha(G),\alpha(H)\}$. Finally, use $\tau(G)=|V(G)|-\alpha(G)$ and $\tau(H)=|V(H)|-\alpha(H)$. The expression is the smaller of $|V(G)|+\tau(H)$ and $|V(H)|+\tau(G)$, as asserted. If a component is empty, the arguments still hold: there are no cross-pairs involving its vertices, and its three parameters are zero. $\square$

Worked Examples

Worked Example: A Path Joined to a Single Edge

Let $G$ have vertex set $\{a,b,c\}$ and edge set $\{ab,bc\}$, so $G$ is a path on three vertices. Let $H$ have vertex set $\{x,y\}$ and edge set $\{xy\}$. The join has vertex set $\{a,b,c,x,y\}$ and edge set $\{ab,bc,xy,ax,ay,bx,by,cx,cy\}$. Find its three parameters.

In $G$, the set $\{a,c\}$ is independent and has size $2$. No independent set can contain $b$ together with either neighbor $a$ or $c$, and there are only three vertices, so $\alpha(G)=2$. In $H$, the edge $xy$ prevents selecting both vertices, while either singleton is independent; hence $\alpha(H)=1$. Therefore $\alpha(G\vee H)=\max\{2,1\}=2$.

The largest clique in $G$ is an edge, so $\omega(G)=2$. The two vertices of $H$ form a clique, so $\omega(H)=2$. The formula gives $\omega(G\vee H)=2+2=4$. In fact, $\{a,b,x,y\}$ is a clique: $ab$ and $xy$ are internal edges, and all four cross-edges between $\{a,b\}$ and $\{x,y\}$ occur in the join. A clique of size $5$ would need all three vertices of $G$ to form a clique, but $ac\notin E(G)$. Thus the maximum is indeed $4$.

The graph has $3+2=5$ vertices, so its cover number is $5-2=3$. To verify this, $\{x,y,b\}$ covers every edge: $x,y$ cover $xy$ and every cross-edge, while $b$ covers $ab$ and $bc$. A cover of size $2$ would have an independent complement of size $3$, which is impossible because the independence number is $2$. Thus $\tau(G\vee H)=3$.

Check: the displayed independent set $\{a,c\}$ has size $2$, the displayed clique $\{a,b,x,y\}$ has size $4$, and the displayed cover $\{x,y,b\}$ has size $3$. Their sizes agree with the formulas and the cover-complement identity $5-2=3$.

Worked Example: A Four-Cycle Joined to a Triangle with a Pendant Vertex

Let $G$ have vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34,41\}$. Let $H$ have vertex set $\{p,q,r,s\}$ and edge set $\{pq,qr,rp,rs\}$. Thus $G$ is a four-cycle, and $H$ consists of a triangle with a vertex $s$ attached to $r$. The join has all eight vertices, the eight internal edges just listed, and every cross-edge $ij$ with $i\in\{1,2,3,4\}$ and $j\in\{p,q,r,s\}$.

The set $\{1,3\}$ is independent in $G$, and no three vertices of the four-cycle are independent: each vertex is adjacent to its two cycle-neighbors, leaving no three pairwise nonadjacent vertices. Hence $\alpha(G)=2$. In $H$, $\{p,s\}$ is independent, since $ps\notin E(H)$. Any three-vertex subset of $H$ contains at least two vertices of the triangle $\{p,q,r\}$, which are adjacent, so $\alpha(H)=2$. It follows that $\alpha(G\vee H)=\max\{2,2\}=2$.

In $G$, every clique has at most two vertices because there is no triangle, and an edge is a clique, so $\omega(G)=2$. The triangle $\{p,q,r\}$ is a clique in $H$, and $s$ is not adjacent to $p$ or $q$, so $\omega(H)=3$. Therefore $\omega(G\vee H)=2+3=5$. For example, $\{1,2,p,q,r\}$ is a clique: $12$ is an edge, $p,q,r$ form a triangle, and all six cross-pairs are edges of the join. A larger clique would have to use more than two vertices from $G$ or more than three from $H$, which is impossible.

There are eight vertices in the join, so the cover formula gives $\tau(G\vee H)=8-2=6$. For a direct cover, take all four vertices of $G$ together with $\{p,r\}$. The set $\{p,r\}$ covers $H$: it meets $pq$ at $p$, $qr$ at $r$, $rp$ at both endpoints, and $rs$ at $r$. The four selected vertices of $G$ cover every cross-edge at its $G$-endpoint. Thus this is a cover of size $4+2=6$. A cover of size at most $5$ would leave at least three vertices outside it, forming an independent set of size at least $3$, contrary to the computed independence number $2$.

Check: $\alpha=2$, $\omega=5$, and $\tau=6$. The sets $\{1,3\}$, $\{1,2,p,q,r\}$, and $V(G)\cup\{p,r\}$ witness the claimed sizes, and $8-2=6$ verifies the cover value.

Worked Example: Unequal Independence Numbers

Let $G$ have vertex set $\{a,b,c\}$ and edge set $\{ab,bc,ca\}$, a triangle. Let $H$ have vertex set $\{u,v,w,z\}$ and edge set $\{uv,vw,wz\}$, a path on four vertices. In $G\vee H$, retain these seven internal edges and add every cross-edge $ij$ with $i\in\{a,b,c\}$ and $j\in\{u,v,w,z\}$.

In the triangle, an independent set has at most one vertex, and a singleton is independent, so $\alpha(G)=1$. In $H$, $\{u,w\}$ is independent, and no three vertices are independent: among any three selected vertices of a four-vertex path, at least one of the edges $uv,vw,wz$ has both endpoints selected. Hence $\alpha(H)=2$, and $\alpha(G\vee H)=\max\{1,2\}=2$.

The triangle has clique number $3$, while the path has clique number $2$: it contains edges but no triangle. Thus $\omega(G\vee H)=3+2=5$. The set $\{a,b,c,u,v\}$ is a clique, using the triangle, the edge $uv$, and all cross-edges between the selected sides. No clique can be larger, since it can use at most three vertices from $G$ and at most two from $H$.

The join has $3+4=7$ vertices, so $\tau(G\vee H)=7-2=5$. Explicitly, $\{a,b,c,v,z\}$ is a cover. It contains all vertices of $G$, so every cross-edge is covered at its $G$-endpoint; it also covers the internal triangle edges, and $v,z$ cover the path edges $uv,vw,wz$. A cover of size $4$ or less would leave at least $3$ vertices outside it, an independent set of size at least $3$, which the independence calculation rules out.

The alternative cover expression gives the same result. Here $\tau(H)=4-\alpha(H)=2$ and $\tau(G)=3-\alpha(G)=2$, so $\min\{3+2,4+2\}=\min\{5,6\}=5$. This agrees with the directly constructed cover and the complement calculation $7-2=5$.

How the Cover Formula Can Be Used

The cover formula has a useful construction behind it. If a cover $C_H$ of $H$ is chosen, then $V(G)\cup C_H$ covers the join: it covers internal edges of $G$ using all of $V(G)$, internal edges of $H$ using $C_H$, and cross-edges using their endpoints in $V(G)$. This gives a cover of size $|V(G)|+\tau(H)$. Reversing the roles gives one of size $|V(H)|+\tau(G)$, so the minimum of these two quantities is an upper bound. The theorem proves that one of these constructions attains the minimum.

Equivalently, a maximum independent set in the join is a maximum independent set from one side, not a combination of independent sets from both sides. Taking its complement gives a minimum cover. This viewpoint explains why comparing the two component independence numbers is the key step.

Common Mistakes

Adding the independence numbers is wrong. In the first example, one might add $\alpha(G)=2$ and $\alpha(H)=1$ and claim an independent set of size $3$. But combining $\{a,c\}$ with $x$ fails: $a$ and $x$ are adjacent in the join, and $c$ and $x$ are adjacent as well. The correct formula is the maximum, giving $\max\{2,1\}=2$.

Forgetting which endpoints cover cross-edges can invalidate an explanation. The set $V(G)\cup C_H$ covers cross-edges because it contains every $G$-vertex, so each cross-edge is covered at its $G$-endpoint. It need not contain the $H$-endpoint of every cross-edge. For instance, the cover $\{a,b,c,v,z\}$ in the third example contains all vertices of $G$ and the cover $\{v,z\}$ of $H$; its size is $3+2=5$, and the stated endpoint argument applies to every cross-edge.

Finally, the clique formula is a sum, not a maximum: a clique from each side can be joined because every cross-pair is adjacent. The proofs rely on the defining all-to-all set of cross-edges; if only some cross-edges are added, these formulas need not hold.

Check Your Understanding

Use the join definition and the three formulas to answer each question. When checking a claimed set, verify its internal and cross-edges separately.

Let $G$ be an edgeless graph on three vertices and $H=K_2$. What are $\alpha(G\vee H)$, $\omega(G\vee H)$, and $\tau(G\vee H)$?
Explain why a nonempty independent set in $G\vee H$ cannot meet both $V(G)$ and $V(H)$.
Let $G=K_3$ and $H$ be a path on four vertices. Give a maximum clique and a minimum vertex cover in the join.
Prove directly that $\tau(G)=|V(G)|-\alpha(G)$ for every finite simple graph $G$.
If $H$ has no vertices, what does $G\vee H$ equal, and how do the three parameter formulas reduce?