A Maximum-Degree Lower Bound for Independence

The Maximum-Degree Bound

An independent set is a collection of vertices with no edges between them. A useful way to build one is to keep adding vertices while possible, stopping only when every vertex left out is adjacent to one already chosen. Such a set need not be as large as possible, but its neighborhood reaches every vertex. Counting that coverage gives a lower bound that depends only on the graph’s order and maximum degree.

Throughout, $G=(V,E)$ is a finite, simple, nonempty graph, with order $n=|V|$, maximum degree $\Delta=\Delta(G)$, and independence number $\alpha(G)$. An independent set is maximal if no vertex can be added to it while keeping it independent. It is maximum if it has the largest cardinality among all independent sets. Maximum implies maximal, but maximal does not in general imply maximum.

Definition: For a vertex $v$, its neighborhood $N(v)$ is the set of vertices adjacent to $v$. Its closed neighborhood is $N[v]=N(v)\cup\{v\}$. Thus $|N[v]|=\deg(v)+1$. The independence number $\alpha(G)$ is the largest size of an independent set in $G$.

Theorem: If $G$ has order $n\ge 1$ and maximum degree $\Delta$, then $$ \alpha(G)\ge \frac{n}{\Delta+1}. $$ Since $\alpha(G)$ is an integer, this also gives $\alpha(G)\ge \left\lceil n/(\Delta+1)\right\rceil$.

The denominator is $\Delta+1$, not $\Delta$: a chosen vertex can account for itself as well as for its neighbors. The proof makes this precise by showing that the closed neighborhoods of a maximal independent set cover the whole vertex set.

Why Maximality Gives a Cover

Proposition: An independent set $I$ in a finite graph is maximal if and only if every vertex outside $I$ has a neighbor in $I$.

Proof. Suppose first that $I$ is maximal. If some $x\notin I$ had no neighbor in $I$, then adding $x$ would create no edge within $I\cup\{x\}$. This would be a larger independent set, contradicting maximality. Conversely, suppose every vertex outside $I$ has a neighbor in $I$. If a larger independent set contained $I$, it would contain some vertex $x\notin I$. But $x$ is adjacent to a vertex in $I$, so that larger set would not be independent. Hence $I$ is maximal. $\square$

Because the graph is finite, a maximal independent set exists: start with the empty set and add an eligible vertex whenever one is available. Each addition increases the size by one, and there are only $n$ vertices. When no addition is possible, the resulting independent set is maximal.

The proposition says exactly that, for a maximal independent set $I$, every vertex is either in $I$ or adjacent to a vertex in $I$. In other words, the closed neighborhoods $N[v]$, for $v\in I$, cover $V$. This is a covering statement; the closed neighborhoods may overlap, so their sizes need not add to exactly $n$.

Proof of the Bound

Proof. Choose a maximal independent set $I$, which exists because $G$ is finite. By the proposition, every vertex of $G$ belongs to $N[v]$ for at least one $v\in I$. Therefore the union of these closed neighborhoods is $V$, and the size of a union is at most the sum of the sizes of its sets:

n=|V| \le \sum_{v\in I}|N[v]| =\sum_{v\in I}\bigl(\deg(v)+1\bigr) \le \sum_{v\in I}(\Delta+1) =|I|(\Delta+1).

Since $\Delta+1>0$, division gives $|I|\ge n/(\Delta+1)$. The independence number is the largest size of any independent set, so $\alpha(G)\ge |I|\ge n/(\Delta+1)$. Finally, an integer at least $n/(\Delta+1)$ must be at least its ceiling, which proves the rounded version as well. $\square$

This proof establishes more than the existence of one suitably large independent set: every maximal independent set has size at least $n/(\Delta+1)$. It does not assert that every maximal independent set has maximum size. The examples illustrate both the bound and that distinction.

Worked Example: A Star and the Difference Between Maximal and Maximum

Let $G$ have vertex set $V=\{c,1,2,3\}$ and edge set $E=\{c1,c2,c3\}$. This is a star with center $c$. Its order is $n=4$; the center has degree $3$, each other vertex has degree $1$, and therefore $\Delta=3$.

The bound gives $n/(\Delta+1)=4/(3+1)=1$, so it guarantees an independent set of size at least $1$. The set $I=\{c\}$ is independent. It is maximal because each vertex outside $I$ is adjacent to $c$. Its closed neighborhood is $N[c]=\{c,1,2,3\}$, which covers all four vertices. Thus this particular maximal set has size $1$, exactly the bound.

However, $I$ is not maximum: the set $\{1,2,3\}$ is independent and has size $3$. No independent set can have size greater than $3$, because any set containing $c$ can contain none of $1,2,3$, while a set not containing $c$ has at most those three vertices. Hence $\alpha(G)=3$, which is greater than the guaranteed lower bound $1$.

Check: the degree calculation gives $\Delta+1=3+1=4$, and $n/(\Delta+1)=4/4=1$. The maximal set has size $1$, while the maximum independent set has size $3$; both satisfy the theorem’s claim about $\alpha(G)$.

Worked Example: Disjoint Triangles Attain the Bound

Let $G$ have vertex set $V=\{1,2,3,4,5,6\}$ and edge set $E=\{12,13,23,45,46,56\}$. The graph consists of two disjoint triangles. It has $n=6$, and every vertex has degree $2$, so $\Delta=2$.

The lower bound is $n/(\Delta+1)=6/(2+1)=2$. Choose $I=\{1,4\}$. Its vertices lie in different components, so they are not adjacent; hence $I$ is independent. The closed neighborhoods are $N[1]=\{1,2,3\}$ and $N[4]=\{4,5,6\}$. Together they cover all six vertices, so $I$ is maximal and has size $2$.

To check that the bound is attained by the independence number, note that an independent set contains at most one vertex from each triangle: every pair within a triangle is an edge. Thus every independent set has size at most $2$. The set $\{1,4\}$ has size $2$, so $\alpha(G)=2$.

Check: the cover count is $|N[1]|+|N[4]|=3+3=6$, and $2(\Delta+1)=2(2+1)=6$. The bound gives $\alpha(G)\ge 6/3=2$, matching the directly verified value $\alpha(G)=2$.

Worked Example: A Path Where the Bound Is Not Exact

Let $G$ have vertex set $V=\{1,2,3,4,5\}$ and edge set $E=\{12,23,34,45\}$, the path $P_5$. The two end vertices have degree $1$, the other three have degree $2$, so $n=5$ and $\Delta=2$.

The theorem gives $\alpha(G)\ge 5/(2+1)=5/3$. Since $\alpha(G)$ is an integer, $\alpha(G)\ge\lceil 5/3\rceil=2$. The set $I=\{2,5\}$ is independent because $25\notin E$. Its closed neighborhoods are $N[2]=\{1,2,3\}$ and $N[5]=\{4,5\}$, whose union is $V$. Thus $I$ is maximal and has size $2$.

In fact, $\{1,3,5\}$ is independent, so $\alpha(G)\ge3$. To verify that no independent set is larger, group the vertices into $\{1,2\}$, $\{3,4\}$, and $\{5\}$. Each of the first two pairs is an edge, so an independent set can take at most one vertex from each pair and at most one from the singleton. Therefore its size is at most $1+1+1=3$, and $\alpha(G)=3$.

Check: the maximal set has size $2$, meeting the rounded guarantee $\lceil5/3\rceil=2$, while the maximum set has size $3$. The bound is valid but not exact for this graph.

Interpreting and Using the Bound

The estimate is strongest when $\Delta$ is small relative to $n$. A vertex in a maximal independent set can cover at most $\Delta+1$ vertices through its closed neighborhood. Covering all $n$ vertices therefore requires at least $n/(\Delta+1)$ chosen vertices. This explanation is the counting argument in words; it does not require the closed neighborhoods to be disjoint.

For a graph with $\Delta=0$, every vertex is isolated: an edge would give its endpoints positive degree. Consequently $V$ itself is independent, $\alpha(G)=n$, and the bound gives $n/(0+1)=n$. This also shows why including the vertex itself in the closed neighborhood matters: here each closed neighborhood consists of exactly one vertex.

One use of the result is as a guaranteed benchmark. It supplies a lower bound on $\alpha(G)$ without requiring a search for a maximum independent set. A particular maximal independent set, found by successive additions, already meets the bound. The argument does not say that such a set is largest; the star example shows why that distinction matters. The bound concerns a guaranteed size, not a method for identifying a maximum set.

Common Counting Pitfall

A tempting mistake is to count only the neighbors of each selected vertex and claim that each one accounts for at most $\Delta$ vertices. For the star in the first example, this would give the incorrect inequality $4\le |I|\cdot3$ and the purported lower bound $\alpha(G)\ge4/3$. The flaw is that $N(c)$ contains only $\{1,2,3\}$: it omits the selected vertex $c$ itself. The correct set to count is $N[c]$, which has size $\deg(c)+1=3+1=4$. In general, maximality gives a cover by closed neighborhoods, not necessarily by open neighborhoods. Thus the correct estimate is $n\le |I|(\Delta+1)$.

A second point to keep straight is the final rounding. The real-valued estimate $\alpha(G)\ge n/(\Delta+1)$ does not mean that the integer $\alpha(G)$ equals that fraction. It means that $\alpha(G)$ is at least its ceiling. In the path example, $5/3$ is not a possible set size, and the integer guarantee is $2$.

Check Your Understanding

For each question, distinguish a maximal set from a maximum set and use closed neighborhoods when applying the counting argument.

Why does a maximal independent set $I$ satisfy $V=\bigcup_{v\in I}N[v]$?
A nonempty graph has $n=10$ and $\Delta=3$. What integer lower bound does the theorem give for $\alpha(G)$?
Give an example of a maximal independent set that is not maximum, and explain why it is nevertheless subject to the theorem’s guarantee.
For the graph with $V=\{a,b,c,d\}$ and $E=\{ab,bc,cd\}$, calculate $n$, $\Delta$, and the rounded lower bound for $\alpha(G)$.
What goes wrong if the proof counts $N(v)$ instead of $N[v]$?