OAI.TriangleFace198.triangle_expansion_face

The theorem states that for a finite loopless multigraph G (each edge e has distinct endpoints left e and right e) and a vertex v incident to exactly three edges, and assuming G has at least one perfect matching (a hypothesis not otherwise used), there is a labelling c of the edges by Fin 3 = {0,1,2} such that each label is carried by exactly one edge incident to v, with the following properties. Let H be the triangle expansion of G at v: v is replaced by a triangle on three new vertices (v itself and two extra vertices), each old edge keeps its other endpoint but any endpoint equal to v is moved to the triangle vertex with the edge's label, and three new edges i in Fin 3 are added, edge i joining triangle vertices i+1 and i+2. Let f be the linear map from edge-weight vectors of G to those of H that keeps the weight on each old edge and gives new edge i the weight of the unique edge at v labelled i. Let Q be the set of points of the matching polytope of H (the convex hull of perfect-matching indicator vectors) whose total weight on edges crossing the cut around the three triangle vertices equals 1. Then f maps the matching polytope of G exactly onto Q; Q is convex and is an extreme subset (a face) of H's polytope; restricting f(x) to the old edges recovers x; f(oldRestriction y)=y for every y in Q; f(x) agrees with x on old edges and with the labelled local edges on new edges; f sends the all-1/3 vector to the all-1/3 vector; and for every x in G's polytope, the minimal face of H's polytope containing f(x) is the image under f of the minimal face of G's polytope containing x, where the minimal face is the intersection of all convex extreme subsets containing the point.