J. Misra’s comment on EWD964

J.Misra's comment on EWD964

Theorem In an undirected graph with N vertices where each vertex is connected to at most m others, every maximal independent set has at least $N / (m + 1)$ vertices. (A set of vertices is independent means that no two vertices in the set are connected. An independent set is maximal means that every vertex outside the set is connected to some vertex inside the set.)

Proof Let s be any maximal independent set, let s be the remaining set of vertices, and let n be the number of edges connecting a vertex from s to a vertex from s . Then

$n \leq \left| s\right| \cdot m,$ because each vertex in $S$ is con- nected to at most m others $\left| \overline{5}\right| \leq n,$ because,since $s$ is maximal,every vertex in $\overline{s}$ is incident on some edge connecting $s$ to $\overline{s}$

Hence,

$$ \begin{array}{l} N = | s | + | \overline {{s}} | \leq | s | + n \leq | s | + | s | \cdot m \ \therefore | s | \geq N / (m + 1) \ \end{array} $$

(End of Proof.)

Also Jaap van der Woude found a proof using the notion of maximal independent sets. Without using that notion J.Misra demonstrated the existence of an independent set of size $\geq N / (m + 1)$ as follows.

Proof Start with enough pigeonholes, all unoccupied. Scan the vertices sequentially in some order and place them in pigeonholes as follows. Each pigeonhole that is occupied contains a vertex that is its leader. A vertex is placed in an occupied pigeonhole only if it is connected to the leader of that pigeonhole; only if a vertex cannot be placed in an occupied pigeonhole it is placed in a new pigeonhole of which it is designated the leader. This algorithm has the invariant

all vertices in a pigeonhole are connected to the leader of that pigeonhole and no two leaders are connected.

At the termination of the procedure, no pigeonhole has more than $m + 1$ vertices (from the connectivity constraint). Therefore, there are at least $N / (m + 1)$ occupied pigeonholes, whose leaders form an independent set. (End of Proof.)

This is a nice constructive proof of my original theorem.

Austin 8 Jannani 1987

prof.dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 United States of America