# Properties of Gomory-Hu trees

Given an undirected graph $$G=(V,E)$$ a Gomory-Hu tree $$T$$ for $$G$$ has the following properties:

• $$T$$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut separating the corresponding pair of vertices of G.
• $$T$$ has the property that the minimum cut between vertices $$s$$ and $$t$$ in $$G$$ is the cut corresponding to the minimum weight edge along the path from $$s$$ to $$t$$ in the Gomory-Hu tree.

In $$[1]$$, the author states the following lemma:

Let $$S$$ be the union of cuts in $$G$$ associated with $$n$$ edges of $$T$$. Then removal of $$S$$ from $$G$$ leaves a graph with at least $$n+1$$ components.

Consider a complete graph $$K_4$$ with all the edges having weight $$1$$.
A (possible) Gomory-Hu Tree $$T$$ for $$K_4$$ is the following:

If we remove the cuts associated with all the $$n=3$$ edges of $$T$$ we might proceed as follows:

• $$(3,0) \in T$$ $$\rightarrow$$ remove $$\{(3,0),(3,1),(3,2)\} \in G$$
• $$(3,1) \in T$$ $$\rightarrow$$ remove $$\{(3,0),(3,1),(3,2)\} \in G$$
• $$(3,2) \in T$$ $$\rightarrow$$ remove $$\{(3,0),(3,1),(3,2)\} \in G$$

A potential result (among the different ones) is a graph with $$2 \neq (n+1=4)$$ connected components, i.e., $$\{3\}$$ and $$\{1,2,4\}$$.
So, my question is, am I missing something in the definition or properties of the Gomory-Hu trees?
Does the author mean that for each $$(u,v)$$ in $$T$$, all the minimum weight cuts between $$u$$ and $$v$$ in $$G$$ should be removed in order for the lemma to hold?

[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013

• When you are saying "union of cuts", does it mean "union of cut sets"? Meaning of Cut-set: the set of edges that goes across the cut. Commented Jan 10, 2021 at 20:13

The book states the following definition of a cut:

a cut is defined by a partition of $$V$$ into two sets say $$V^{l}$$ and $$V \setminus V^{l}$$ and consists of all edges that have one endpoint in each partition.

Therefore, removing a cut from the graph should mean that we are removing the edges that go across the cut.

Also, consider the following definition of the "cut associated with an edge $$(u,v) \in T$$ in $$G$$".

Each edge $$(u,v)$$ in $$T$$ denotes a partition of $$V$$ given by the two connected components obtained by removing $$(u,v)$$ from $$T$$. Consider the cut defined in $$G$$ by this partition. We will say that this is the cut associated with $$(u,v)$$ in $$G$$.

Now, let us consider your example of Gomory-Hu tree for $$K_{4}$$. We want to find the cut associated with the edge $$(3,0) \in T$$. If we remove $$(3,0)$$ from $$T$$, we obtain the partitioning $$\{1,2,3\}$$ and $$\{0\}$$. This defines the cut in $$G$$. Therefore, you should be removing the edges of $$G$$ that goes across this cut i.e., $$(0,1)$$ $$(0,2)$$ and $$(0,3)$$.

Similarly for the edge $$(3,1) \in T$$, you should be removing the edges: $$(1,0)$$, $$(1,2)$$, and $$(1,3)$$.

And, for the edge $$(3,2) \in T$$, you should be removing the edges: $$(2,0)$$, $$(2,1)$$, and $$(2,3)$$.

It means we are removing all edges from the graph. Therefore, the number of connected components in the remaning graph would be $$4 = (n + 1)$$, for $$n = 3$$.

• Nice, I had totally missed the definition of cut associated with (𝑢,𝑣) in 𝐺.
– abc
Commented Jan 10, 2021 at 20:47