Braced Polygon

The braced square problem asks, given a hinged square composed of four equal rods (indicated by the red lines above), how many more hinged rods must be added in the same plane (with no two rods crossing) so that the original square is rigid in the plane? The best solution known (left figure above), uses a total of 27 rods (including four for the square), where , , and are collinear (Gardner 1964; Gardner 1984; Wells 1991; Fredrickson 2002, p. 70, Fig. T4).

Configurations corresponding to rigid graphs with equal-length edges (which can without loss of generality be taken to have unit lengths) and continaing a regular polygon as a subgraph are known as braced (regular) polygons. While the original variant of the problem assumined non-overlapping rods and hence corresponds to graph embedings that are rigid and matchstick graphs, loosening the condition to allow overlapping edges gives solutions corresponding to rigid unit-distance graphs.

For example, if rods are allowed to cross to form a braced square, the best known solution, due to A. Khodulyov and illustrated above, requires 19 rods (Friedman 2006).

In 1963, T. H. O'Beirne found matchstick solutions for the pentagon using 69 rods, for the octagon using 113 rods, and for the dodecagon using 57 rods (Fredrickson 2002, p. 70). O'Beirne's pentagon bracing is shown above (Fredrickson 2002, p. 71, Fig. T6).

It is possible to brace a square without using triangles. The 21-edge, 12-node, unit-distance graph illustrated above and constructed via vertex-deletion from a certain 29-node symmetric braced graph (Pegg 2018b) is triangle-free and braces two squares (E. Pegg, pers. comm., Jan. 3, 2021). Furthermore, any rigid framework (and hence all regular polygons) can be converted to a triangle-free equivalent by chaining copies of the 12 12-vertex triangle-free braced square shown above along the two collinear edges gives (P. Taxel, Jan. 3, 2021).

The following table (updated from Friedman 2006, and with the 36-edge Mireles graph, which is not rigid, removed) gives smallest known solutions as of Oct. 2021, both with and without overlapping rods. Many of these are implemented in the Wolfram Language as GraphData["BracedSquare",27,1], GraphData["BracedPentagon",69,1], etc.

Khodulyov's solutions for the heptagon and 11-gon are just instances of an "equal angles" method using Peaucellier-Lipkin linkages that works for all -gons with (with the exceptions of , 9, 10, and 12, which produce vertex-vertex degenerate embeddings). The result is asymptotically optimal and requires rods (J. Tan, pers. comm., Oct. 26, 2021).

	edges	matchstick	edges	unit-distance
3	3	triangle graph (trivial)	3
4	27	seven discoverers (Gardner 1964)	19	Andrei Khodulyov (Friedman 2006)
5	69	T. H. O'Beirne in 1963 (Fredrickson 2002, p. 70)	31	Andrei Khodulyov (Friedman 2006)
6	11	Friedman (2006; trivial)	11
7			35	Ed Pegg, Jr., Parcly Taxel, W. R. Somsky (Dec. 2020)
8	113	T. H. O'Beirne in 1963 (Fredrickson 2002, p. 70)	31	Andrei Khodulyov (Friedman 2006)
9			51	Andrei Khodulyov (Friedman 2006)
10			55	Andrei Khodulyov (Friedman 2006)
11			79	J. Tan (Parcly Taxel 2021)
12	57	T. H. O'Beirne in 1963 (Fredrickson 2002, p. 70)	49	Andrei Khodulyov (Friedman 2006)
13			151	J. Tan (Oct. 2021)
14			91	W. Somsky (Dec. 2020)
15			231	Andrei Khodulyov (J. Tan, Oct. 2021)
16			109	J. Tan (Oct. 2021)
17			269	Andrei Khodulyov (J. Tan, Oct. 2021)
18			117	J. Tan (Oct. 2021)