Concepts of betweenness in graph theory

Given a metric space, then metric betweenness can be defined by the metric betweenness formula. This states that a point is between two points if it going to through that point doesn't increase the distance to the endpoints, in other words, if it is in the shortest path between the two points. In the particular case of graphs, their metric can be defined by the shortest path length. Then this concept from the theory of metric spaces can be applied to the special case of graph theory.

$d(x,y)=d(x,z)+d(y,z)$

The actual formula $d(x,y)=d(x,z)+d(y,z)$ should be familiar from the triangle inequality, which is an axiom of the definition of metric spaces. It states that the distance between two points is less then the distance between the two points and a midpoint or it is equal to them in which case it is between them. With this in mind, the axioms of a metric space make perfect sense. The metric betweenness is the main concept of metrics used in both graph theory and metric geometry in general. A different notion is total betweenness defined by all paths rather then just the shortest paths.

Total betweenness:
The most basic context in which to consider total betweenness is trees, where there is only a single path between any two points. In this context, the total betweenness and the metric betweenness coincide. So for example, with a path graph the central vertex is between its two neighbors.


Total betweenness is totally defined by the cut vertices of a graph. To see this, consider that it is only when one reaches a cut vertex then one must make a choice of which direction to go to, which can limit the number of vertices that can be reached between any two points. In a biconnected graph, any points can be reached in a path between any other one. As a consequence, the total betweenness is entirely determined by the block cut tree of the graph. Given any two distinct vertices, all vertices in paths between them can be produced by determining all blocks and cut vertices between the two points in the block cut tree. As this is merely a process of determining betweenness on a tree which is determined by metric betweenness, it can be said that the metric definition is the main form of betweenness worth considering.

Metric betweenness:
Perhaps the simplest case to consider where metric betweenness is different then total betweenness is the case of the cycle graph on five elements. Given two non-adjacent points on this graph, there is a path between them of length three and another one of length four. All the points are between them in the context of total betweenness, but only one of them is under metric betweenness. This demonstrates that metric betweenness can give us more information in some cases.



Once we have a concept of betweenness like this, it is useful to consider convex sets, which are subsets of the graph in which all points between them are contained within the set. A closed metric interval is defined by the set of all points between them plus the endpoints. This leads to a better understanding of subsets of a graph. There is also a concept of betweenness on partial orders, which isn't considered here. This demonstrates how useful betweenness relations can be to a variety of different subjects in mathematics.