Lo, On-Hei SolomonOn-Hei SolomonLoSchmidt, Jens M.Jens M.Schmidt2020-10-192020-10-192018-1229th International Symposium on Algorithms and Computation (ISAAC 2018) 123: 38 (2018)http://hdl.handle.net/11420/7605Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely mind(v), d(w), where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree δ contains Ω(δ2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree δ ≥ 5 or with edge-connectivity λ ≥ 4 or with vertex-connectivity κ ≥ 3 contains in fact Ω(δ|V |) pendant pairs. We prove that this bound is tight from several perspectives, and that Ω(δ|V |) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.enAnd phrases Pendant PairsGomory-Hu TreeMaximal Adjacency OrderingMaximum Cardinality SearchPendant TreeTesting Edge-ConnectivityConference Paper10.4230/LIPIcs.ISAAC.2018.38Conference Paper