= Solution
For $A\subseteq E$, write $x(A)=\sum_{e\in A}x_e$, and let $\kappa(A)$ count the connected components of $(V,A)$, including isolated vertices. A maximal <forest> in each component has one fewer <edge> than vertices, so $r(A)=|V|-\kappa(A)$. The required <forest polytope> is
$$
\boxed{P=\{x\in\mathbb R^E:x_e\geq0\ (e\in E),\quad x(A)\leq |V|-\kappa(A)\ (A\subseteq E)\}.}
$$
We prove both inclusions, using the <matroid independence polytope> argument explicitly.
If $I$ is a <forest>, $I\cap A$ is an independent <subset> of $A$, so $\mathbf1_I(A)=|I\cap A|\leq r(A)$. Its indicator is nonnegative. All <convex combinations> of these indicators therefore lie in $P$.
For the converse, take any real objective vector $c$. List just its positive-weight <edges> as $e_1,\ldots,e_k$ with $c_1\geq\cdots\geq c_k>0$, put $c_{k+1}=0$, and set $S_i=\{e_1,\ldots,e_i\}$. Run the <forest> greedy <algorithm> on these <edges> and call the output $I$. At every prefix, the accepted <edges> form a maximal <forest> of $(V,S_i)$, so
$$
|I\cap S_i|=r(S_i).
$$
Indeed a previously rejected <edge> still has its endpoints joined later; therefore no rejected prefix <edge> can augment the chosen <forest>. A maximal <forest> spans every prefix component and has the stated size.
For every $x\in P$, dropping nonpositive objective terms and telescoping now gives
$$
\begin{aligned}
c^Tx
&\leq\sum_{j=1}^kc_jx_{e_j}
=\sum_{i=1}^k(c_i-c_{i+1})x(S_i)\\
&\leq\sum_{i=1}^k(c_i-c_{i+1})r(S_i)
=c^T\mathbf1_I.
\end{aligned}
$$
The last equality uses the same telescoping identity for the greedy indicator. If there are no positive coefficients, the empty <forest> attains the bound zero. Thus \b[every linear objective over $P$ is maximized by a <forest> indicator].
The <singleton> inequalities give $0\leq x_e\leq r(\{e\})\leq1$, so $P$ is <compact>. The <convex hull> $Q$ of the finitely many <forest> indicators is also <compact>. If some $x\in P$ were outside $Q$, the finite-dimensional <separating hyperplane theorem> would give $c$ with $c^Tx>\max_{y\in Q}c^Ty$, contradicting the bound just proved. Therefore $P\subseteq Q$, completing the convex-hull proof.
An equivalent system indexed by vertex sets is
$$
\boxed{x_e\geq0,\qquad x(E(S))\leq |S|-1\quad(\varnothing\ne S\subseteq V),}
$$
where $E(S)$ contains all <edges> with both ends in $S$. The rank system implies this since $r(E(S))\leq|S|-1$. Conversely, split any <edge> set $A$ into its vertex components $S_1,\ldots,S_t$. Nonnegativity and the vertex inequalities give $x(A)\leq\sum_jx(E(S_j))\leq\sum_j(|S_j|-1)=|V|-\kappa(A)$. Hence this second system describes the same polytope.
Back to article page
