The sharp vertex bound
for conditional decomposability

Proof. The graph has a triangle, since its minimum degree exceeds . Close that triangle under two-neighbor absorption, and suppose the resulting set has size . Every outside vertex has at most one neighbor in it. The degree bound then gives

where the middle expression counts the set and the distinct outside neighbors required by its vertices. But for . The case is a triangle.

For the line version, three pairwise coplanar matching lines are concurrent unless all lie in one plane. In the latter case their witnessing faces would coincide and contain all three matching edges, contrary to the hypothesis. Once two lines through a common point have been obtained, any line cofacial with both must pass through that point; otherwise the same planar contradiction occurs. The preceding two-neighbor ordering therefore propagates concurrence to the entire family. □

Proof. Subtract the homothety on the complement from a nontrivial parallel map. If a facet vertex had two exterior neighbors, its value would be zero. The normal component of the map is constant on the facet, so it would then be zero everywhere on that facet. Every facet vertex has an exterior neighbor; its value is parallel to that exterior edge and has zero normal component, hence vanishes. This would make the whole map trivial. □

Proof. Translate the image into an -space . The map is constant on every edge not parallel to . Choose a functional vanishing on and exposing a vertex of the quotient . A strictly increasing edge path from any vertex ends in that exposed fiber, preserving along the way. Thus each quotient-vertex fiber carries the entire image. A parallel map on a connected face takes values in a translate of its direction space, so each such fiber has dimension exactly .

There are at least disjoint vertex fibers. If all their restrictions were nonhomothetic, Lemma 2 would give

a contradiction. On one fiber the map is therefore with ; the same conclusion is automatic when .

To recover convexity from this one fiber, define on the normal cone of each vertex . Parallelism makes the pieces agree on their common walls. The gradients lie in , so factors through . Choose exposing . For large , a vertex exposed by lies in and maximizes there. Evaluating at this direction therefore gives

Choose the sign so that this factor is convex. A sufficiently small positive multiple can then be subtracted from without losing convexity, giving the required weak summand. □

Proof. The lines of edges joining the two classes concur at the center of their difference. Neither class can be a singleton, since two-neighbor absorption would then make the map homothetic. A center in would make the crossing edges a star or a single edge, contradicting -connectivity. The center is therefore exterior and the crossing edges form a matching of size at most .

Every two-face incident to a crossing edge contains exactly two crossing edges. Distinct two-faces give distinct partners, so the cofaciality graph has minimum degree . Lemma 2 forces a common projective center in every realization. It remains exterior because two disjoint actual edges cannot meet inside the polytope. Choose two distinct homotheties with this difference center; they define a nontrivial parallel map on the two classes in the new realization.

For a segment summand, the summand map takes two values and is already covered by two constant homotheties. □

Proof. Corresponding triangles in the two simplex faces force to be distinct and collinear. In one simplex, with homogeneous vertices , the centers span a hyperplane avoiding all the , and the triangle collinearities put every in it. If defines that hyperplane, set . Then represents . The linear identification turns the into compatible homothety parameters. Distinct parameters and at least two vertices in each class ensure nontriviality. □

Proof. Rescale the summand and write , , . Quotient by the direction space of . Each quotient-vertex fiber contains as a summand and therefore has at least vertices. A vertex of receives the label of its vertex in .

Codimension at least three. Suppose . Since

must be a simplex. At most edges at a vertex change its label, one for each incident simplex edge, so every color has at least vertices. For a fixed simplex edge, its parallel copies form a matching, and

An edge belongs to at least two-faces. At most have a triangular image in , one for each possible third label; every other two-face contains exactly two members of the fixed family. Its cofaciality graph has minimum degree , so Lemma 2 forces its center in every realization.

A quotient-vertex fiber is either a simplex or has at least vertices. If at most one were a simplex, then

For this is impossible, and two simplex fibers give the conclusion by Lemma 6. When , the only remaining equality consists of one triangular and quadrilateral fibers over a quotient simplex, with no additional vertices. The facet opposite the triangle has Shephard’s property; any edge changing quotient position preserves the label, and the triangle has exactly one vertex of each label.

Codimension two. Now . The quotient is a triangle, since four vertex fibers would require vertices. Also

so is indecomposable. Every vertex fiber is homothetic to or has at least vertices, and at least one is homothetic. If these three fibers contain all vertices, the facet opposite a homothetic fiber has Shephard’s property by the same label argument.

Suppose additional vertices occur and one fiber is nonhomothetic. Counting forces two simplex fibers, a -vertex fiber, and one extra vertex . An edge through cannot change its label, since that would require a second vertex at the same quotient point. At most two vertices of its label occur in the simplex fibers and at most in the remaining fiber. Hence is simple. The hyperplane through its neighbors cuts off only , so deletion has a combinatorially determined type with a new simplex facet. It is the preceding Shephard type. In every realization a nontrivial parallel map on the deletion is homothetic on that simplex facet and extends by the same homothety to the restored vertex. Thus restoration preserves universal decomposability.

It remains that all three vertex fibers are homothetic and extra vertices occur. Their convex hull has fibers , where and are affine barycentric interpolants. An extra vertex violates a side inequality

with exposing a facet of . The parallel exposed face of beyond this inequality contains only extra vertices and retains that facet as a summand, so it needs at least vertices. Thus

Equality forces to be a simplex and all extra vertices to form one -simplex , parallel to a facet of , over one nonvertex quotient point. Its labels are precisely those of that facet.

The previous two-face count gives each edge family cofaciality degree at least two. A family involving the missing label has exactly three members, so its lines are forced concurrent. Every other family has four members, including one edge of . A two-face through that edge with triangular image must lie in , because a label-changing edge preserves the quotient position. There are at most such faces. The extra edge therefore has cofaciality degree at least ; the other degrees are at least two. This graph contains minus at most one edge, so two-neighbor propagation forces concurrence. The simplex reconstruction lemma applies.

The three-dimensional endpoint. A planar summand of a three-polytope on at most seven vertices must be a triangle, since its two endpoint fibers already use twice its number of vertices. If one endpoint fiber is not homothetic to the triangle, it has at least four vertices, leaving no others; the opposite facet is Shephard. Otherwise both fibers are homothetic. Any additional vertex would violate a side inequality of their hull, and the exposed face beyond it retains a triangle edge as a summand, requiring two additional vertices. This is impossible. Either endpoint facet is therefore Shephard. □

Proof. At a private vertex , an edge to has in (2); otherwise would also belong to . Thus . The edge star at spans the ambient space, so

Central vertices contribute nothing modulo , and has dimension . □

Proof. Every neighbor of other than its classmates has quotient proportional to , by (2). The star spans the quotient, so every classmate must be a neighbor. Normalize the quotient basis by . For , this functional is nonnegative on all edge rays at and hence on ; varying proves nonnegativity of every .

The sum exposes . At , only the classmate edges leave this face, so its dimension is at least , and the defining projective subspace gives the reverse inequality. At a different , only the edge to can leave , making that face a facet. Their common zero set is . □

Proof. Among the other classes, choose one with . Its vertices are simple; there are at most neighbors within the class and at most one towards each other parameter. At one such vertex take the facet omitting its edge towards . This facet contains the whole minimum class and all difference centers between the other classes. Propagating along their crossing matchings puts at least vertices of every class , , into the facet.

An omitted vertex of such a class has at most neighbors in its own class, at most in the other noncentral classes, and at most one towards . Its degree is therefore at most

which is impossible. All classes other than lie in the facet, and each of their vertices has its unique neighbor outside. Facet connectivity then excludes any vertex inside the facet. This is Shephard’s property. □

Proof. Pass to essential full classes and assign each shared vertex to one of its classes, obtaining a disjoint coloring. Two colors are covered by Lemma 5. If a crossing family is absent, say , subtract and split the resulting map into its restrictions supported on colors 0 and 1. Both are parallel and at least one is nontrivial, giving a two-class map. If the three parameters are collinear, replace them by two values on their common line; every crossing edge still respects the same center, so this also reduces to two classes.

We may therefore assume that the parameters are affinely independent, that all three crossing families are nonempty, and that their distinct centers lie on the line . Lemma 8 gives at least noncentral vertices of each color. If misses , a positive projectivity sends it to infinity and makes the image at most two dimensional. Lemma 4, Lemma 5, and Proposition 7 apply. Henceforth assume .

Forcing an exterior center. An exterior center makes its crossing family a matching. For an edge off , at most one incident two-face has plane containing . Every other incident two-face uses just this family; another family would put two distinct centers in its plane. Such a face contains exactly two members of the matching. Distinct faces give distinct partner edges, so the off-line cofaciality graph has minimum degree .

Once contains vertices, an off-line family with edges uses only noncentral vertices, whence

For , this gives , and Lemma 2 forces its center in every realization. For , and minimum degree one gives two cofacial lines, so they too have a forced intersection. The new center remains exterior, since two disjoint actual edges cannot meet in . We use this argument only after showing that contains a vertex.

A center is a vertex. There cannot be two vertex centers; their owner pairs share a color, and deleting those two vertices disconnects that color’s noncentral vertices from the others, contrary to Balinski’s theorem. Suppose the center of is a vertex , assigned to color 0. If it has no color-0 neighbor, assign it to color 1 instead; the family disappears and we are done. Otherwise has neighbors of both colors 0 and 1.

It has no color-2 neighbor. Such a neighbor would lie on , by (2), and would be unique. Delete its vertex from the vertex figure at . The remaining graph is connected and contains both colors 0 and 1, so has an edge joining them. Its corresponding two-face contains one edge. Parity around its boundary then forces an edge of each other crossing family, so its plane contains and hence the edge . But the two edges of this face at were chosen to avoid , a contradiction.

The other centers must be exterior. Indeed, a center in the interior of an edge has that edge as its sole crossing edge. Parity in two incident two-faces puts on its line. The vertex would then be an endpoint of that edge, giving the forbidden color-2 neighbor. Thus both nonstar families lie off , and the preceding matching argument forces their centers.

The vertex-figure graph is two-connected, so there are at least two edges between its color-0 and color-1 parts. The corresponding two-face planes each contain and an edge of both nonstar families. In every realization their intersection therefore makes and the two reconstructed centers collinear. Three distinct collinear centers give compatible homothety differences. If the two exterior centers coincide, merge colors 0 and 1. Either way a nontrivial parallel map is reconstructed.

No center is a vertex. If a center lies in the interior of an edge , that family consists only of . Every two-face through it uses the other two families by parity, and two such planes show that is the line of . The other centers are exterior, since the same actual edge cannot belong to two families.

The same configuration is forced if all centers are exterior. The graph of crossing edges is a forest. To prove this, a cycle has one constant nonzero quotient direction modulo , so lies in a plane containing . As a cycle of actual polytope edges, it bounds the section of by that plane. Yet every supporting edge line meets outside , which is incompatible with meeting that section. Thus there is no cycle.

Each crossing component spans at most one quotient direction, so there are at least components. Any family containing an off-line edge has at least edges, by its cofaciality degree. If all three did, the forest would have at least vertices. Hence some family consists of the unique edge on .

In both cases, contains the endpoints of , and the matching argument forces the other two centers in every realization. Each two-face through contains an edge of both other families, so two such planes put their centers on the line of . Choose the two homothety differences with these centers. Their third difference is also centered on , and therefore respects the sole remaining crossing edge. Coincident centers give a two-color map. All constructed maps are nontrivial because each color has at least vertices and the homotheties do not all agree. □

Proof. If , Lemma 8 gives

since the concave quadratic has value at both endpoints of . Thus , , and

Some class has no excess, so the fiber faces exist. If , the projective conclusion follows from Section 4.

Assume . If , inequality (3), with and , gives

a contradiction. Hence or .

The case . Now , and (3) forces every central vertex to be shared and to have degree in . Thus is a clique and is a homothety . If were not a given parameter, the ownership sets at different vertices would be disjoint, and at most one vertex could be shared; two lines joining disjoint pairs of affinely independent parameters cannot intersect at . Since , this is impossible. Therefore is a common central class and Lemma 10 applies.

The case . Here and . Lemma 2 makes rigid for , and the case is also rigid. For , any triangle absorbs the remaining vertex, leaving only a central four-cycle as an exception.

First suppose . If is a given parameter, use Lemma 10. Otherwise the ownership sets are disjoint and at most one vertex is shared. A singly owned vertex has degree by (3); a missing edge would therefore have two shared endpoints. It follows that is complete.

If no vertex is shared, one class owns no central vertex. Its vertices supply the fiber faces, each with one noncentral vertex of every color. In each fiber face the vertex is universal, and the other vertices have minimum degree , hence form a connected graph. The cone over a spanning tree is rigid. The noncentral vertices of that fiber form the complement of the facet , so Lemma 3 makes that facet Shephard.

If a central vertex is shared by classes , all other central vertices are singly owned. The minimum - and -fiber systems coincide, since their matchings exhaust any singly owned class. Their two vertices in each fiber share the central vertex and the other row vertices. This contains a rigid , forcing , contrary to essentiality.

It remains that and is a four-cycle. Every central vertex is shared by (3). Along the connected graph of , identity (2) puts its owner parameters in one translate of , of dimension three. Thus at most four classes occur. Their owner pairs are distinct and triangle-free, since a triangle of pairs would give three collinear polytope vertices. They form the cycle , leaving one class unowned. Disjoint owner pairs cannot be adjacent in , because the edge homothety would meet two skew parameter lines; hence this is also the physical cyclic order.

All noncentral vertices are simple. At an vertex take the facet omitting its edge towards class 1. Its homogeneous span is

where . This facet contains exactly

Vertices in and 3 have their unique exterior neighbor in class 1; those in 2 and have it at ; those in 4 and have it at . The facet is therefore Shephard. □

Proof. Fewer essential parameters are covered by Propositions 11 and 12, so assume that all four or five parameters are essential and distinct. The shared vertex is central. If , the class bound would require at least noncentral vertices in addition to , exceeding . Hence and .

The noncentral parts of have exactly two vertices, so all excess lies in , or in . Lemma 9 applies and the central face contains .

For , the budget is . At , inequality (3) gives , so . If , the homothety on that edge is a common central class; otherwise its other endpoint would be singly owned and require excess at least two, whereas . The common class is or , and Lemma 10 applies. If , the other two central vertices belong to ; the homothety on the central triangle would be , giving three owners at , which is impossible.

For , we have and , so . Suppose . The central triangle has a homothety . If is not a given parameter, its three ownership sets are disjoint. The vertex uses , and the other two central vertices belong respectively to . Each original four-set has only one central vertex, so . At most one of those two central vertices can also belong to , leaving a singly owned vertex. Inequality (3) requires excess at least two in its class, whence , contrary to . Thus is a common central class, and Lemma 10 applies.

Suppose . If were homothetic, one of would own two of its vertices and hence its homothety, again giving three owners at . Therefore is nonrigid. A face of dimension at least three with at most five vertices is rigid by Lemma 2, so is a quadrilateral or pentagon.

Both and own central vertices; each original four-set has at least two noncentral vertices, and neither can account for all centers other than . Together with , these are four owner colors. The three-dimensional space allows no fifth, leaving unowned. Since and , equation (3) makes every central vertex shared. Their distinct owner pairs form a triangle-free graph on four colors, forcing and the four-cycle from the proof of Proposition 12.

The sole excess vertex belongs to or ; call this color 1 and use as the unowned class. The hyperplane (5) again gives a Shephard facet, containing the other three classes and the two central vertices . Its two ordinary color-1 vertices lie outside. If the possible third color-1 vertex were inside, it would have no neighbor in the facet; its classmates and incident centers are outside, and every other crossing edge has center outside the hyperplane. Facet connectivity excludes it. This completes both boundary cases. □

Proof. There is a rigid set with at least three vertices. Otherwise the graph would be triangle-free and -free. At a vertex of degree , its independent neighbors require at least outgoing edges, whereas each other vertex can meet at most two of them. Thus . For this forces a three-regular graph on seven vertices, impossible by parity.

Enlarge a rigid set maximally. Its complement has minimum degree two and at most four vertices. A three-vertex complement is a triangle, and a four-vertex complement has a perfect matching and is covered by two rigid edges. This proves the claims. □

Proof of Theorem 1. In dimension three, Lemma 14 supplies at most three rigid pieces, and Proposition 11 applies. The preceding reductions settle every larger dimension. Thus below vertices, any decomposable realization forces decomposability of the whole combinatorial type. Wang and Yost’s construction [5] gives a conditionally decomposable type with exactly vertices in every dimension . □