Forest polytope ($\mathrm{conv}\{1_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 descriptionsHere $\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)\le {\sum }_{j}x(E(S_j))\le {\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.