Sets expressible as unions of two convex sets
William R. Hare, John W. Kenelly · Proceedings of the American Mathematical Society · 1970
A graph-theoretic formulation of McKinney's [1] characterization of the union of two convex sets leads to an especially concise proof, and suggests a technique which may prove quite useful in certain combinatorial-geometric problems. If S is a set in a real linear space, we define the nonvisibility graph G(S) of S as the graph whose vertices are the points of S and whose edges are defined by: if x, yES, then x and y are joined by an edge in G(S) if and only if xy ?S (i.e., x and y are not visible in S). McKinney's property Po translates into the graph-theoretic condition that G(S) has no circuits of odd length. It is a standard theorem (see [2]) that a graph has no circuits of odd length if and only if it is bipartite.