= Forest polytope
{title2=$\operatorname{conv}\{\mathbf1_F:(V,F)\text{ is a forest}\}$}
For an undirected finite <graph>, its <forest> polytope is the <matroid independence polytope> of its <graphic matroid>. It has the exact inequality descriptions
$$
\{x\geq0:x(A)\leq |V|-\kappa(V,A)\text{ for all }A\subseteq E\}
=\{x\geq0:x(E(S))\leq|S|-1\text{ for all nonempty }S\subseteq V\}.
$$
Here $\kappa(V,A)$ counts all <connected components of a graph>, including isolated vertices, and $E(S)$ denotes the <edges> internal to $S$. A maximal <forest> has one fewer <edge> than vertices in each component, giving the rank $|V|-\kappa(V,A)$. The <matroid independence polytope> theorem therefore proves the first description. It implies the second since the rank of $E(S)$ is at most $|S|-1$. Conversely, split any $A$ into its vertex components $S_j$; nonnegativity gives $x(A)\leq\sum_jx(E(S_j))\leq\sum_j(|S_j|-1)=|V|-\kappa(V,A)$. No spanning requirement is imposed, so an optimum with negative <edge> weights can leave vertices isolated.
Back to article page
