Gomory‐Hu trees of infinite graphs with finite total weight.

Abstract: A well‐known theorem of Gomory and Hu states that if <italic>G</italic> is a finite graph with nonnegative weights on its edges, then there exists a tree <italic>T</italic> (now called a Gomory‐Hu tree) on V ( G ) such that for all u ≠ v ∈ V ( G ) there is an e ∈ E ( T ) such that the two components of T − e determine an optimal (minimal valued) cut between <italic>u</italic> an <italic>v</italic> in <italic>G</italic>. In this article, we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one cannot omit the condition of the finiteness of the total weight. [ABSTRACT FROM AUTHOR]