Skeleton of locally most separable 3-terminal graphs

Abstract

A 3-terminal graph is a graph with 3 distinguished vertices, called terminals. Let Tn,m be the set of all connected 3-terminal graphs on n vertices and m edges. Let G be in Tn,m. A spanning subgraph H of G is 3-separable when H has precisely 3 components, each containing one terminal. For each p in [0, 1], the separability of G at p, denoted SG(p), is the probability that the resulting subgraph of G is 3-separable after each edge in G is removed independently with probability 1−p. The graph G is a locally most separable 3-terminal graph (LMS3TG) if for each H in Tn,m there exists δ > 0 such that SG(p) ≥ SH(p) whenever p ∈ (1 − δ, 1). Let Cn,m be the set of all connected simple graphs on n vertices and m edges. For each G in Cn,m, the skeleton G′ of G is the graph arising from G by the contraction of each of its bridges. In this note, we show that the skeleton of each LMS3TG in Tn,m is an almost-complete graph.