Median Graph - Convex Sets and Helly Families

Convex Sets and Helly Families

In a median graph, a set S of vertices is said to be convex if, for every two vertices a and b belonging to S, the whole interval I(a,b) is a subset of S. Equivalently, given the two definitions of intervals above, S is convex if it contains every shortest path between two of its vertices, or if it contains the median of every set of three points at least two of which are from S. Observe that the intersection of every pair of convex sets is itself convex.

The convex sets in a median graph have the Helly property: if F is an arbitrary family of pairwise-intersecting convex sets, then all sets in F have a common intersection. For, if F has only three convex sets S, T, and U in it, with a in the intersection of the pair S and T, b in the intersection of the pair T and U, and c in the intersection of the pair S and U, then every shortest path from a to b must lie within T by convexity, and similarly every shortest path between the other two pairs of vertices must lie within the other two sets; but m(a,b,c) belongs to paths between all three pairs of vertices, so it lies within all three sets, and forms part of their common intersection. If F has more than three convex sets in it, the result follows by induction on the number of sets, for one may replace an arbitrary pair of sets in F by their intersection, using the result for triples of sets to show that the replaced family is still pairwise intersecting.

A particularly important family of convex sets in a median graph, playing a role similar to that of halfspaces in Euclidean space, are the sets

W_uv = {w | d(w,u) < d(w,v)}

defined for each edge uv of the graph. In words, W_uv consists of the vertices closer to u than to v, or equivalently the vertices w such that some shortest path from v to w goes through u. To show that W_uv is convex, let w₁w₂...w_k be an arbitrary shortest path that starts and ends within W_uv; then w₂ must also lie within W_uv, for otherwise the two points m₁ = m(u,w₁,w_k) and m₂ = m(m₁,w₂...w_k) could be shown (by considering the possible distances between the vertices) to be distinct medians of u, w₁, and w_k, contradicting the definition of a median graph which requires medians to be unique. Thus, each successive vertex on a shortest path between two vertices of W_uv also lies within W_uv, so W_uv contains all shortest paths between its nodes, one of the definitions of convexity.

The Helly property for the sets W_uv plays a key role in the characterization of median graphs as the solution of 2-satisfiability instances, below.