= Solution
Let $Z$ be the <set> of <isolated vertices> of the finite <simple graph> $G=(V,E)$. Introduce a nonnegative <integer> $x_v$ for every <vertex>. Use the <integer program>
$$
\boxed{\begin{aligned}
\text{maximize}\quad&\sum_{v\in V}x_v\\
\text{subject to}\quad&x_u+x_v\leq1&&\text{for every }\{u,v\}\in E,\\
&x_v\leq1&&\text{for every }v\in Z,\\
&x_v\geq0,\quad x_v\in\mathbb Z&&\text{for every }v\in V.
\end{aligned}}
$$
Every nonisolated <vertex> belongs to an <edge>, whose inequality and the other endpoint's nonnegativity already imply $x_v\leq1$. The explicit bounds on $Z$ therefore make all variables binary. For an <integer> <feasible point>, $S=\{v:x_v=1\}$ is an <independent set>, and its <cardinality> is the objective. Conversely the <indicator vector> of any <independent set> is feasible. Thus \b[the optimal value is the maximum <independent set> size]. Including the isolated-<vertex> bounds is essential for an arbitrary <graph>; without them the formulation would be unbounded whenever an <isolated vertex> is present.
Back to article page
