Universal Inequalities for Independence, Clique, and Coloring

Three Parameters, Three Universal Bounds

A graph’s independent sets and cliques describe opposite local patterns: an independent set has no edges within it, while a clique has every possible edge. A proper coloring divides the vertices into independent sets. These connections yield useful bounds that hold for every finite simple graph, regardless of its structure. They can give quick checks on proposed parameter values and show how one parameter constrains another.

Throughout, $G=(V,E)$ is a finite simple graph, with order $n=|V|$. A set $S\subseteq V$ is independent if no two vertices in $S$ are adjacent. A clique is a set of vertices in which every two distinct vertices are adjacent. The independence number $\alpha(G)$ is the maximum size of an independent set, and the clique number $\omega(G)$ is the maximum size of a clique. “Maximum” means largest cardinality, not merely a set that cannot be extended.

Definition: A proper coloring assigns a color to each vertex so that adjacent vertices receive different colors. The chromatic number $\chi(G)$ is the minimum number of colors in a proper coloring. We use the convention $\alpha(G)=\omega(G)=\chi(G)=0$ when $V=\varnothing$. For a nonempty graph, $\alpha(G)\ge1$ and $\chi(G)\ge1$.

In a proper coloring, the vertices of each one color form an independent set. Conversely, placing an independent set in one color creates no conflict among its vertices. The bounds below use the first observation directly and the second to construct a coloring.

The Universal Inequalities

Theorem: For every finite simple graph $G$ of order $n$, $$ \omega(G)\le \chi(G),\qquad \alpha(G)\chi(G)\ge n,\qquad \chi(G)\le n-\alpha(G)+1. $$

Proof. If $V=\varnothing$, all three parameters and $n$ are zero by convention, and the inequalities read $0\le0$, $0\ge0$, and $0\le1$. Now suppose $V\ne\varnothing$.

Take a clique of size $\omega(G)$. Each pair of its distinct vertices is adjacent, so every pair must receive different colors in any proper coloring. Thus at least $\omega(G)$ colors are required, giving $\omega(G)\le\chi(G)$.

Fix a proper coloring using $\chi(G)$ colors, and let its color classes be $C_1,\ldots,C_{\chi(G)}$. These classes partition $V$, and each is independent, so $|C_i|\le\alpha(G)$ for every $i$. Therefore $$ n=\sum_{i=1}^{\chi(G)}|C_i| \le\sum_{i=1}^{\chi(G)}\alpha(G) =\alpha(G)\chi(G). $$ This proves the product bound.

Finally, choose an independent set $S$ of maximum size, so $|S|=\alpha(G)$. Give all vertices of $S$ one color, and give each vertex in $V\setminus S$ its own separate color. No two vertices in $S$ are adjacent, and every vertex outside $S$ has a distinct color, different from the color on $S$. This is a proper coloring using $1+(n-\alpha(G))$ colors. Since $\chi(G)$ is the minimum number needed, $\chi(G)\le n-\alpha(G)+1$. $\square$

The middle inequality can also be read as $\alpha(G)\ge n/\chi(G)$ for a nonempty graph. Since $\alpha(G)$ is an integer, this implies $\alpha(G)\ge\lceil n/\chi(G)\rceil$. The first inequality says that a large clique forces many colors; the last says that a large independent set gives a direct way to use fewer colors. These are bounds, not generally equalities.

Worked Examples

Worked Example: A Triangle with a Pendant Vertex

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,13,23,14\}$. Compute the parameters and check all three bounds.

Vertices $1,2,3$ form a triangle, so $\omega(G)\ge3$; vertex $4$ is not adjacent to $2$ or $3$, so no four vertices form a clique. Thus $\omega(G)=3$. The triangle requires three different colors, and the coloring $1\mapsto A,\ 2\mapsto B,\ 3\mapsto C,\ 4\mapsto B$ is proper, so $\chi(G)=3$.

An independent set contains at most one of $1,2,3$, since those vertices form a triangle. If it contains $1$, it cannot contain $4$, so it has size at most one. If it contains $2$ or $3$, it may also contain $4$, giving size at most two. The set $\{2,4\}$ is independent, hence $\alpha(G)=2$. The order is $n=4$.

Check: Substitution gives $\omega(G)=3\le3=\chi(G)$, $\alpha(G)\chi(G)=2\cdot3=6\ge4=n$, and $\chi(G)=3\le4-2+1=3$. The first and third bounds are equalities, while the product bound is strict.

Worked Example: Two Disjoint Edges and an Isolated Vertex

Let $G$ have $V=\{1,2,3,4,5\}$ and $E=\{12,34\}$. Vertex $5$ is isolated. Find $\alpha(G)$, $\omega(G)$, and $\chi(G)$.

An independent set can contain at most one endpoint of $12$, at most one endpoint of $34$, and can include $5$. Hence its size is at most $1+1+1=3$. The set $\{1,3,5\}$ is independent, so $\alpha(G)=3$. A clique can contain at most the two endpoints of one edge: there is no edge between vertices from different edges or between $5$ and any other vertex. Thus $\omega(G)=2$.

At least two colors are needed because $12\in E$. Assign color $A$ to $1,3$, color $B$ to $2,4$, and either color to the isolated vertex $5$. This is proper, so $\chi(G)=2$. Here $n=5$.

Check: The three inequalities become $2\le2$, $3\cdot2=6\ge5$, and $2\le5-3+1=3$. In particular, the product bound need not be an equality, even when the clique bound is.

Worked Example: Two Triangles Joined by an Edge

Let $G$ have $V=\{1,2,3,4,5,6\}$ and $E=\{12,13,23,45,46,56,34\}$. Thus $1,2,3$ form one triangle, $4,5,6$ form another, and $34$ joins the triangles.

Each triangle is a clique, so $\omega(G)\ge3$. There is no clique of size four: a clique using vertices from both triangles would need to contain both $3$ and $4$, the only edge between the triangles, but neither $1$ nor $2$ is adjacent to $4$, and neither $5$ nor $6$ is adjacent to $3$. Therefore $\omega(G)=3$.

Because a triangle needs three colors, $\chi(G)\ge3$. The assignment $1\mapsto A,\ 2\mapsto B,\ 3\mapsto C,\ 4\mapsto A,\ 5\mapsto B,\ 6\mapsto C$ is proper: each triangle has three different colors, and the joining edge $34$ has colors $C$ and $A$. Hence $\chi(G)=3$.

An independent set contains at most one vertex from each triangle, so it has size at most two. The set $\{1,5\}$ is independent because there is no edge $15$, so $\alpha(G)=2$. The order is $n=6$.

Check: The bounds give $3\le3$, $2\cdot3=6\ge6$, and $3\le6-2+1=5$. The product bound is tight here, while the final bound leaves room for two additional colors beyond the actual chromatic number.

How the Bounds Fit Together

The three inequalities give a chain and a product constraint: $$ \omega(G)\le\chi(G)\le n-\alpha(G)+1, \qquad \alpha(G)\chi(G)\ge n. $$ The chain implies $\omega(G)\le n-\alpha(G)+1$ as well: the first inequality gives $\omega(G)\le\chi(G)$, and the third gives $\chi(G)\le n-\alpha(G)+1$. This consequence is useful as a consistency check on proposed values of $\omega(G)$, $n$, and $\alpha(G)$.

The last bound has a constructive meaning. A maximum independent set can all share one color, and every remaining vertex can be assigned its own color. It is an upper bound because this particular coloring works; it does not claim that the coloring is optimal. A graph may allow vertices outside the chosen independent set to share colors, as in the two-triangles example.

Common Mistake: Substituting the Clique Number

The product inequality uses $\alpha(G)$, not $\omega(G)$. For the graph with edges $12$ and $34$ and isolated vertex $5$, we computed $\omega(G)=2$, $\chi(G)=2$, and $n=5$. Replacing $\alpha(G)$ by $\omega(G)$ would incorrectly suggest $2\cdot2\ge5$, but $4<5$. The correct calculation uses $\alpha(G)=3$, giving $3\cdot2=6\ge5$. The reason is structural: each color class is an independent set, so its size is bounded by $\alpha(G)$, not by the size of a largest clique.

Another point to keep straight is the direction of the coloring bounds. A clique forces distinct colors and therefore gives a lower bound on $\chi(G)$. A constructed coloring gives an upper bound. The product bound comes from partitioning all vertices into color classes, each of size at most $\alpha(G)$.

Check Your Understanding

Use the definitions and the three proved bounds to answer these questions.

For a nonempty graph with $\alpha(G)=4$ and $\chi(G)=3$, what lower bound does the product inequality give on $n$?
Why must every clique receive distinct colors in a proper coloring?
In the two-triangles example, identify an independent set of maximum size and explain why a larger one cannot exist.
For a graph of order $8$ with $\alpha(G)=3$, what upper bound does the theorem give on $\chi(G)$?
Explain why the color classes in a proper coloring can each be used in the proof of $\alpha(G)\chi(G)\ge n$.