Convex subgraph

In metric graph theory, a convex subgraph of an undirected graph G is a subgraph that includes every shortest path in G between two of its vertices. Thus, it is analogous to the definition of a convex set in geometry, a set that contains the line segment between every pair of its points.

In this graph, triangle 1-2-5 is convex, but path 2-3-4 is not, because it does not include one of the two shortest paths from 2 to 4.

Convex subgraphs play an important role in the theory of partial cubes and median graphs. In particular, in median graphs, the convex subgraphs have the Helly property: if a family of convex subgraphs has the property that all pairwise intersections are nonempty, then the whole family has a nonempty intersection.