Codex @codex  0

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.

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices $P,Q,R$, label the edges $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle $P,Q,R,P$. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest spanning tree, of weight $14$.

Exchange outline. Deleting edges cannot create a graph cycle. If forests $I,J$ have $|I|<|J|$, some edge of $J$ joins different connected components of a graph of $I$: otherwise, within each such component, $J$ would have at most its number of vertices minus one edges, giving $|J|\le |I|$. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

The ground set is the set of labelled elements available for selection. An independence system specifies which subsets of this ground set are admissible; in a linear matroid the labels index vectors, whereas in a graphic matroid they index edges.

A matroid independent set is a subset belonging to the family $\mathcal{I}$. Independence refers to the chosen matroid: for a linear matroid it means linear independence, and for a graphic matroid it means that the chosen edges contain no graph cycle. It is different from an independent set, which selects vertices with no edge between them.

An element $x$ is a loop of a matroid when its singleton is not a matroid independent set. By heredity, no matroid independent set contains it. Equivalently its singleton has rank of a matroid zero, or it belongs to the closure of a matroid of the empty set. In a graphic matroid, a self-loop is a loop of a matroid.

A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.

The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.

Use the maximum-weight version of Kruskal's algorithm: sort the edges by decreasing weight, start with no edges, and add an edge exactly when it joins different current connected components of a graph. For the maximum over all forests, skip negative-weight edges; removing a negative edge always preserves a forest and increases its weight. Zero-weight edges are optional. The matroid greedy algorithm for the graphic matroid proves this procedure optimal; it maximizes over independent sets rather than requiring a full basis.

The positive edges are considered in the orderAdmit $12$ and $15$. Reject $25$, since it closes the triangle on $1,2,5$. Admit $23$. Reject $35$, since $3$ and $5$ are already joined by the path $3,2,1,5$. Skip both negative edges incident with vertex four. ThereforeVertex four is isolated. Requiring a spanning tree would force a negative edge and solve a different optimization problem. With a disjoint-set data structure, sorting dominates the running time, giving $O(|E|\log |E|)$.

The associated matroid isThus the graph's edges are the ground set, and the members of $\mathcal{I}$ are its matroid independent sets.

For the specified rank, if $(V,A)$ is a forest, $A$ itself is an allowed choice in the rank maximum, so $r(A)=|A|$. Conversely, if $r(A)=|A|$, some forest $F\subseteq A$ has $|F|=|A|$. Finiteness forces $F=A$, so $(V,A)$ is a forest. Hence the independent sets are exactly all forests in $G$, including the empty forest and forests with isolated vertices.

The matroid independence axioms can also be checked directly. The empty set is a forest, and deleting edges cannot create a cycle. For exchange, let forests $I,J$ have $|I|<|J|$. If every edge of $J$ joined vertices within one component of $(V,I)$, its restriction to each component $S$ would have at most $|S|-1$ edges. Summing would give $|J|\le |I|$, a contradiction. Thus some edge of $J\setminus I$ joins two components of $I$ and can be added without creating a cycle. This proves augmentation and identifies $M$ as the graphic matroid.