Dudeney’s Dissection Is Optimal

Demaine, Erik D.; Kamata, Tonan; Uehara, Ryuhei

doi:10.4230/LIPIcs.ITCS.2026.47

Dudeney’s Dissection Is Optimal

Erik D. Demaine

Massachusetts Institute of Technology, Cambridge, MA, USA Tonan Kamata

Japan Advanced Institute of Science and Technology, Ishikawa, Japan Ryuhei Uehara

Japan Advanced Institute of Science and Technology, Ishikawa, Japan

Abstract

In 1907, Henry Ernest Dudeney posed a puzzle: “cut any equilateral triangle … into as few pieces as possible that will fit together and form a perfect square” (without overlap, via translation and rotation). Four weeks later, Dudeney demonstrated a beautiful four-piece solution, which today remains perhaps the most famous example of dissection. In this paper (over a century later), we finally solve Dudeney’s puzzle, by proving that the equilateral triangle and square have no common dissection with three or fewer polygonal pieces. We reduce the problem to the analysis of discrete graph structures representing the correspondence between the edges and the vertices of the pieces forming each polygon.

Keywords and phrases:

Geometric Dissection, Dudeney Dissection, Dissection with Fewest Pieces

Funding:

Tonan Kamata: is mainly supported by JSPS KAKENHI Grants Number 22J10261 and 24K23857, and partially supported by Grants Number 20H05961 and 20H05964, and by JST ACT-X Grant Number JPMJAX25C8.

Ryuhei Uehara: is mainly supported by JSPS KAKENHI Grants Number 24H00690 and partially supported by Grants Number 22H01423, 20H05961, and 20H05964.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Randomness, geometry and discrete structures ; Mathematics of computing

\rightarrow

Discrete mathematics

Related Version:

Full Version: https://arxiv.org/abs/2412.03865

Acknowledgements:

The authors would like to thank the members of the Tokyo-based math club “sugakuday,” a group that describes itself as a gathering of people who like math – or don’t. During a visit by Tonan Kamata, a discussion with the group – particularly with Motcho Ajisaka and Fueruma (@motcho_tw, @fueruma_suugaku on

\mathbb{X}

) – led to the discovery of an oversight in the enumeration of square dissections in the previous version of this paper. We express our deep respect for their open, playful, and curiosity-driven community.

DOI:

10.4230/LIPIcs.ITCS.2026.47

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Dissection [15, 9] is the process of transforming one shape $A$ into another shape $B$ by cutting $A$ into pieces and re-arranging those pieces to form $B$ (without overlap). Necessarily, $A$ and $B$ must have the same area (a property Euclid used to prove area equalities). Conversely, every two polygons of the same area have a dissection – a result from over two centuries ago [16, 18, 2, 13]. The number of pieces cannot be bounded as a function of the number of vertices (consider, for example, dissecting an $N\times N$ square into an $N^{2}\times 1$ rectangle), but there is a pseudopolynomial upper bound [1].

Given two specific polygons, can we find the dissection between them with the fewest possible pieces? In general, this minimization problem is NP-hard, even to approximate within a factor of $1+1/1080-\varepsilon$ [3]. Worse, the existence of a $k$ -piece dissection is not known to be decidable, even for $k=2$ pieces [3]. A core difficulty is that the number of cut segments has no obvious upper bound, even for 2-piece dissection. The special case where the $k=2$ pieces must be mirror congruent to each other has a polynomial-time decision algorithm [8], even though the number of cuts cannot be bounded as a function of $n$ [17].

Instances of the dissection problem have captivated puzzle creators and solvers for centuries; see [9, 12] for much history. One pioneer was English puzzlist Henry Ernest Dudeney [11], who published many dissection puzzles in newspapers and magazines in the late 19th and early 20th centuries [6, 7]. Over the years, geometric puzzlers continually improved the records for the fewest-piece dissections between various pairs of polygons. Harry Lindgren (an Australian patent reviewer) collected many of these results and improved most of them in his book [15]. He wrote:

“In a few cases (very, very few) it could perhaps be rigorously proved that the minimum number has been attained, and in a few more one can feel morally certain; in all the rest it is possible that you may find a dissection that is better than those already known” [15, p. 1]

Some past work determines the asymptotic growth of the number of pieces for certain infinite families. Cohn [4] showed that a triangle of diameter $d$ needs $\Theta(d)$ pieces to dissect into a unit square, where the constant in the $\Theta$ is between $0.7415$ and $1$ . (The obvious diameter lower bound is $d/\sqrt{2}\approx 0.7071\,d$ .) Kranakis, Krizanc, and Urrutia [14] showed that the regular $n$ -gon needs $\Theta(n)$ pieces to dissect into a square, where the constant in the $\Theta$ is between $1/4$ and $1/2$ .

In this paper, we give the first nontrivial proof of exact optimality of the number of pieces in a dissection, by proving optimality of the famous four-piece dissection of an equilateral triangle to a square shown in Figure 1. Dudeney [5] posed this dissection as a puzzle on April 6, 1902, without making it especially clear whether he had a solution. In the next issue of his column (April 20), he described an easy five-piece solution, wrote that Mr. C. W. McElroy of Manchester had found a four-piece solution, and gave readers another two weeks to try to find it. No one did, leading Dudeney to conclude that “the puzzle may be regarded as a decidedly hard nut” in the next issue where he gave the four-piece solution (May 4). It remains unclear whether this solution was originally invented by Dudeney or McElroy [9, 10]. The puzzle and solution appeared later in Dudeney’s book as “The Haberdasher’s Puzzle” [6, Puzzle 26]; Gardner [11] called it “Dudeney’s best-known geometrical discovery”.

Figure 1: The four-piece dissection between an equilateral triangle and a square [5].

Since this discovery over 120 years ago, it has remained open whether this dissection is optimal, or whether the record will someday be improved upon (as many other records have) [5, 1, 3]. In this paper, we finally settle this problem:

Theorem 1.

There is no dissection with three or fewer polygonal pieces between a square and an equilateral triangle, when we forbid flipping pieces.

Figure 1 also does not require the pieces to be flipped, but this is not necessarily a requirement in the original puzzle. When first teasing “the correct solution”, Dudeney wrote, “surprising as it may seem, it is not necessary to turn over any piece.” So we leave an intriguing puzzle for future work: is there a 3-piece dissection if we allow flipping pieces? We also do not know whether curved pieces might help, though we suspect Theorem 1 extends to both of these settings.

Overview

The structure of the proof is as follows. First, it is relatively easy to show that a two-piece dissection is impossible (see Lemma 14). Thus, we focus on proving the impossibility of a three-piece dissection. To do so, we classify the finitely many possible topologies for cutting each polygon that could potentially result in a three-piece dissection. Next, we use fundamental properties of dissections to narrow down the feasible combinations of these cutting topologies for the two shapes. Finally, we show that all remaining combinations are infeasible using the new concepts of “matching diagrams”, which handle the potentially unbounded number of cut segments.

This paper is organized as follows. We start in Section 2 with basic definitions of dissections, specifically the graph of cuts within each shape, and a categorization of vertices in these graphs into six types. Then, in Section 3, we introduce our primary tool for analyzing dissections – vertex and edge matching diagrams – and prove several general necessary properties for dissections to work, which can be applied to other dissection problems as well. Next, in Section 4, we give a technical overview of our proof, and illustrate by describing one key case in detail; this section gives a flavor of our techniques without getting bogged down in the many cases necessary to complete the proof (but from a technical perspective, it can be skipped). Finally, in Section 5, we give the full proof, which applies the matching diagrams from Section 3 to the specific case of the equilateral triangle and the square.

2 Preliminaries

We define a polygon to be a connected region in the plane of finite area bounded by finitely many line segments. (This definition does not require polygons to be simple, although we will show in Lemma 16 that our main proof can consider just simple polygons.) We refer to a polygon’s line segments as sides and the intersections of these sides as corners.¹¹1We use these terms (instead of more common terms such as “edges” and “vertices”) to provide unambiguous terminology for edge- and node-like features of various parallel structures: polygons, cut graphs, and matching graphs. The boundary of a polygon consists of the corners and points along the sides, while the interior is all other points within the region. Let $\|s\|$ denote the Euclidean length of a side $s$ , and let $\angle(x)$ denote the interior angle of the region at corner $x$ .

A $𝒌$ -piece dissection of a pair of polygons $(P,P^{\prime})$ consists of $k$ polygons $P_{1},P_{2},\ldots,P_{k}$ and two sets of corresponding congruence transformations ${\lambda_{1},\lambda_{2},\ldots,\lambda_{k}}$ and ${\lambda^{\prime}_{1},\lambda^{\prime}_{2},\ldots,\lambda^{\prime}_{k}}$ such that $\bigsqcup_{i}\lambda_{i}(P_{i})=P$ and $\bigsqcup_{i}\lambda^{\prime}_{i}(P_{i})=P^{\prime}$ .²²2The notation $\sqcup$ denotes interior-disjoint set union, i.e., we allow the polygons to overlap on shared boundaries. Figure 1 is an example of a 4-piece dissection. We refer to $P$ and $P^{\prime}$ as target shapes, and $P_{1},P_{2},\ldots,P_{k}$ as pieces. Naturally, the areas of the target shapes must be equal to the total area of the pieces.

A dissection of $(P,P^{\prime})$ divides each target shape $X\in\{P,P^{\prime}\}$ into pieces by cut lines. We define a finite geometric graph called the cut graph $G^{X}$ , which represents the cut lines and the boundary of $X$ . Specifically, $G^{X}$ has faces that correspond one-to-one with the pieces, vertices $V(G^{X})$ which consist of the corners of $X$ and the points along the cut lines having at least one surrounding angle not equal to $\pi$ , and edges $E(G^{X})$ which consist of the cut and boundary lines connecting these vertices. For example, Figure 1 highlights the vertices and edges of $G^{P}$ and $G^{P^{\prime}}$ for Dudeney’s four-piece dissection. The edges $E(G^{X})$ either originate from cut lines, referred to as internal edges, or from the sides of $X$ , referred to as boundary edges. The vertices $V(G^{X})$ are intersections between at least two edges; a vertex met only by internal edges is an internal vertex, while a vertex met by at least one boundary edge is a boundary vertex. Based on the elements surrounding each vertex of $G^{X}$ , we classify boundary vertices into Types 1–2 and internal vertices into Types 3–6 as follows (refer to Figure 2):

$\blacksquare$

Type 1: Corner vertex. A boundary vertex corresponding to a corner of the target shape $X$ .
$\blacksquare$

Type 2: Side vertex. A boundary vertex corresponding to a point along a side of the target shape $X$ .
$\blacksquare$

Type 3: Paired vertex. An internal vertex where exactly two piece corners meet.
$\blacksquare$

Type 4: Convex vertex. An internal vertex where three or more piece corners meet, and all interior angles are convex.
$\blacksquare$

Type 5: Reflex vertex. An internal vertex where three or more piece corners meet and only one of them is reflex.
$\blacksquare$

Type 6: Flat vertex. An internal vertex where at least two piece corners and one piece side meet.

Figure 2: The types of vertices in

G^{X}

: Type 1 to 6 (left to right).

This distinction will be useful in Section 5.1 when counting the number of angles appearing in the cut graph.

We define a subdivision of the cut graph $G^{X}$ to be a graph obtained by replacing internal edges of $G^{X}$ with paths consisting of paired (Type 3) vertices. We define an equivalence relation $\sim$ where $G^{X}_{0}\sim G^{X}_{1}$ if there exist subdivisions $H^{X}_{0}$ and $H^{X}_{1}$ of the graphs $G^{X}_{0}$ and $G^{X}_{1}$ respectively, and a bijection $\phi:V(H^{X}_{0})\rightarrow V(H^{X}_{1})$ such that $\phi$ is a graph isomorphism that disregards geometry while preserving vertex types.

3 Matching Diagram

When a set of pieces is assembled to form a target shape, each side of a piece corresponds to an edge of the cut graph, and each corner corresponds to a vertex of the cut graph. Therefore, when a pair of target shapes has a dissection, there are two corresponding relationships: one between the edges and another between the vertices of the cut graph. In this section, we formalize these relationships and describe these properties.

3.1 Edge Matching Diagram

When analyzing the relationship between the sides of pieces and the edges of the cut graph, the fundamental principle is that boundary edges correspond to a single side of a piece, while interior edges correspond to two sides from different pieces. However, this correspondence becomes more complex in the vicinity of flat vertices. For instance, when there is a flat vertex on the side of a piece, two sides of the pieces correspond to this side (see the left of Figure 3). Moreover, when multiple flat vertices are adjacent on the graph, more complex correspondences arise (see the middle and right of Figure 3).

Figure 3: Examples of flat vertices affecting the edge correspondence, and the corresponding nodes in the edge matching diagram.

To systematically represent these relationships, we introduce a bipartite diagram. In this diagram, each side of a piece is treated as a link, and the edges of the cut graph are treated as nodes. The endpoints of each link are the nodes representing the edges, which correspond to the sides indicated by the links. This construction ensures that an edge corresponding one-to-one to two sides becomes a degree-2 node, while all other edges become degree-1 nodes. In cases where a side crosses multiple edges due to flat vertices, we introduce virtual nodes (see the red lines in the left and the middle of Figure 3). In contrast, edges of the cut graph that do not correspond to any piece side are removed from the node set (see the red dotted line in the right of Figure 3). We now formalize this construction as follows:

Definition 2.

We define an edge matching diagram $\mathscr{ED}$ for a pair of cut graphs $G^{P}$ and $G^{P^{\prime}}$ (see Figure 4) as follows:

$\blacksquare$
For each $X\in\{P,P^{\prime}\}$ , define the node set $N^{X}(\mathscr{ED})$ as follows:
- –
  
  Initialize $N^{X}(\mathscr{ED})$ as $E(G^{X})$ .
- –
  
  For an edge $x\in N^{X}(\mathscr{ED})$ , if both endpoints of $x$ in the cut graph are flat vertices and an angle of $\pi$ appears on opposite sides of $x$ , then remove $x$ from $N^{X}(\mathscr{ED})$ .
- –
  
  For each side of a piece $x$ , if there is a flat vertex on $x$ when forming $X$ , add a new corresponding node to $N^{X}(\mathscr{ED})$ .
$\blacksquare$

Let $L(\mathscr{ED})$ be the set of links between $N^{P}(\mathscr{ED})$ and $N^{P^{\prime}}(\mathscr{ED})$ , connecting a link for each side $e\in E(P_{1})\cup E(P_{2})\cup\cdots\cup E(P_{k})$ according to the correspondence between links representing the sides of pieces and nodes representing the edges of the graph.

Figure 4: The edge matching diagram of Dudeney’s dissection from Figure 1.

The added nodes corresponding to a flat vertex are called flat nodes, nodes corresponding to boundary edges are called boundary nodes, and all other nodes are called internal nodes. We use terms such as degree, leaf, and path for the diagram in the same way as they are used in standard graph theory.

By construction, the degree of each node in $\mathscr{ED}$ is either $1$ or $2$ . Moreover, since two sides sharing a degree-2 node correspond to the same edge of a cut graph, their Euclidean lengths are equal. Consequently, a path can be obtained by iteratively following degree-2 nodes starting from a leaf of $\mathscr{ED}$ ; this path satisfies the following property:

Observation 3.

For any path in $\mathscr{ED}$ , all piece sides corresponding to the nodes along the path have equal Euclidean lengths.

3.2 Vertex Matching Diagram

Next, we consider the relationships between the corners of the pieces and the vertices of the cut graph. This relationship can be considered more simply compared to the relationships between edges discussed in Section 3.1. A corner of a piece corresponds to a vertex in the cut graph $G^{X}$ of each target shape $X\in\{P,P^{\prime}\}$ . Conversely, when looking at the vertices of $G^{X}$ , one or more piece corners may coincide. To capture this relationship, we introduce the following definition:

Definition 4.

We define a vertex matching diagram $\mathscr{VD}$ for $G^{P}$ and $G^{P^{\prime}}$ (see Figure 5):

$\blacksquare$

For each $X\in\{P,P^{\prime}\}$ , define the node set $N^{X}(\mathscr{VD})$ as $V(G^{X})$ .
$\blacksquare$

Let $L(\mathscr{VD})$ be the set of links between $N^{P}(\mathscr{VD})$ and $N^{P^{\prime}}(\mathscr{VD})$ by connecting a link for each corner $x\in V(P_{1})\cup V(P_{2})\cup\cdots\cup V(P_{k})$ according to the correspondence between links representing the corners of pieces and nodes representing the vertices of the graph.

Figure 5: The vertex matching diagram of Dudeney’s dissection from Figure 1.

Since each node of $\mathscr{VD}$ corresponds to a vertex of the cut graph, we define the terms corner, side, paired, convex, reflex, and flat directly for the nodes as well.

We define a weight $\omega(x)$ for each node $x$ of $\mathscr{VD}$ by the sum of the interior angles of the corners that gather at $v$ . The value of $\omega(x)$ is $2\pi$ if $x$ is a paired, convex, or reflex vertex. In the case that $x$ is a flat or side node, $\omega(x)$ is $\pi$ . In the case that $x$ is a corner node, $\omega(x)$ is the interior angle of the corresponding corner of the target shape.

We can also observe the following by the fact that a paired vertex, which is shared by two corners, has a weight of $2\pi$ :

Observation 5.

For any path in $\mathscr{VD}$ that consists of paired vertices, $\angle(x)+\angle(x^{\prime})=2\pi$ or $\angle(x)=\angle(x^{\prime})$ holds depending on whether the length of the path is odd or even, where $x$ and $x^{\prime}$ are the corners corresponding to the endpoint nodes of the path.

Figure 6: Relationship between the interior angles in a path of

\mathscr{VD}

composed of paired vertices. The red and blue marks represent the nodes of

\mathscr{VD}

, and the dotted lines connecting them represent links, that is, corners of the pieces.

Taking the union of the piece vertices gathered at each node sets $N^{P}(\mathscr{VD})$ and $N^{P^{\prime}}(\mathscr{VD})$ , we can count the piece vertex set in two different ways, revealing the following fact:

Observation 6.

Any connected component $C$ of $\mathscr{VD}$ satisfies

\sum_{x\in N(C)\cap N^{P}(\mathscr{VD})}\omega(x)=\sum_{x\in N(C)\cap N^{P^{% \prime}}(\mathscr{VD})}\omega(x).

3.3 Relationship between Vertex and Edge Matching Diagrams

This section describes the relationship between paths in the edge and vertex matching diagram, which are generated by sides and their endpoint corners. Formally, when a side of a piece is placed along the horizontal axis with the inside of the piece facing downward, the corner on the right is referred to as clockwise next, while the one on the left is referred to as counterclockwise next. The same definitions apply to the corners as viewed from a side.

The following lemma describes the relationship between a path in $\mathscr{ED}$ , starting from a side, and the $\mathscr{VD}$ path formed by the corners that come next along the boundary of the target shape.

Lemma 7.

Let $e$ and $e^{\prime}$ be links in $\mathscr{ED}$ , that is, sides of pieces, and assume that they are connected by a path in $\mathscr{ED}$ . Let $v_{1}$ and $v_{2}$ be the clockwise and counterclockwise next corners of $e$ , respectively. Similarly, define $v^{\prime}_{1}$ and $v^{\prime}_{2}$ for $e^{\prime}$ . Here, $v_{1}$ is connected to either $v^{\prime}_{1}$ or $v^{\prime}_{2}$ by a path in $\mathscr{VD}$ , and $v_{2}$ is connected to the other.

Proof.

Based on the assumption that $e$ and $e^{\prime}$ are connected by a path in $\mathscr{ED}$ , each node along this path corresponds to a one-to-one pairing of two sides of the pieces. Since these two sides form an a single edge of the cut graph, the vertices at both endpoints of this edge correspond to the corners of the respective sides. Therefore, there exists a pair of paths in $\mathscr{VD}$ that shares a node between the pairs of corners to which the two next sides correspond. $\hfill\blacktriangleleft$ Note that which pair corresponds depends on whether the piece is flipped or not. When any piece is not flipped, it is possible to precisely describe which pair corresponds. This will be discussed in Section 3.4.

Next, we consider the relationship between a $\mathscr{VD}$ path and the $\mathscr{ED}$ paths formed by the next sides of the corner in the $\mathscr{VD}$ path. Before describing this relationship, we define some terminology. Let us consider a paired vertex $x$ of $G^{X}$ such that both adjacent vertices are non-flat. In this case, pairs of the next sides of the corner corresponding to $x$ create degree-2 nodes in $\mathscr{ED}$ (see the left of Figure 7). On the other hand, in other cases – such as when $x$ is a corner vertex, a side vertex, a flat vertex, or a paired vertex adjacent to a flat vertex – one pair of sides does not correspond to each other and remain as degree-1 nodes, while the other pair corresponds to a degree-2 node (see the middle of Figure 7). In particular, when passing through a side vertex that bisects a side $e$ of a piece, the sum of the Euclidean lengths of the disconnected paths is equal to the Euclidean length of $e$ (see the right of Figure 7).

Figure 7: Examples illustrating the relationship between

\mathscr{VD}

and

\mathscr{ED}

paths.

Based on these observations, we introduce the following definition:

Definition 8.

We introduce the following notations (see Figure 8):

$\blacksquare$

$N^{X}_{\mathit{dit}}(\mathscr{VD})\subset N^{X}(\mathscr{VD})$ denotes the union of side vertices whose adjacent vertices are both corner vertices and of flat vertices whose adjacent vertices are both paired vertices. These are referred to as divide-in-two vertices.
$\blacksquare$

$N^{X}_{\mathit{bur}}(\mathscr{VD})\subset N^{X}(\mathscr{VD})$ denotes the set of paired vertices such that both adjacent vertices are non-flat. These are referred to as buried vertices.

Then, a path $P=(p_{1},\ldots,p_{k})$ of $\mathscr{VD}$ is well-behaved if $p_{2},\ldots,p_{k-1}\in N^{X}_{\mathit{dit}}(\mathscr{VD})\cup N^{X}_{\mathit{% bur}}(\mathscr{VD})$ .

Figure 8: Left: The points marked with a solid black circle are in

N^{X}_{\mathit{dit}}(\mathscr{VD})

, while those with a dotted black circle are not. Similarly, the point marked with a solid red circle is in

N^{X}_{\mathit{bur}}(\mathscr{VD})

, while that with a dotted red circle is not. Right: A well-behaved path of

\mathscr{VD}

and its along sequence.

Using the above definition, the relationship between a $\mathscr{VD}$ path and its adjacent $\mathscr{ED}$ paths can be expressed by the following lemma:

Lemma 9.

Let $P$ be a well-behaved path in $\mathscr{VD}$ , $v$ be an end node of $P$ , and $e$ be the next side of $v$ . We define an along sequence $M_{1},\ldots,M_{k}$ of paths in $\mathscr{ED}$ as follows:

$\blacksquare$

Each $M_{j}$ is a path in $\mathscr{ED}$ , and the end node of $M_{1}$ is $e$ .
$\blacksquare$

A pair of adjacent edges – one ending $M_{j}$ and the other starting $M_{j+1}$ – share a point in $N^{X}_{\mathit{dit}}(\mathscr{VD})$ on a side $L_{i}$ as one of their end nodes.

Then, the alternating sum of $\|e\|,\|L_{1}\|,\|L_{2}\|,\ldots,\|e^{\prime}\|$ is zero where $e^{\prime}$ is the end node of $M_{k}$ .

Proof.

The side $e$ and part of $L_{1}$ share a path in $\mathscr{ED}$ , and according to Observation 3, their Euclidean lengths are equal. Moreover, the remaining part of $L_{1}$ and part of $L_{2}$ also share a path in $\mathscr{ED}$ , and these Euclidean lengths are equal as well. The equality of all these parts implies that the alternating sum of the Euclidean lengths is zero. $\hfill\blacktriangleleft$

3.4 Lemmas when Flipping is not Allowed

When flipping of a piece is not allowed, the relationship between the connected components in Lemma 7 can be described based on the length of the paths as follows:

Lemma 10.

We use the same notation as in Lemma 7. Let $C_{1}$ and $C_{2}$ be connected components of $\mathscr{VD}$ , where $v_{1}\in C_{1}$ and $v_{2}\in C_{2}$ .

$\blacksquare$

If the length of $P$ is odd, then $v^{\prime}_{2}\in C_{1}$ and $v^{\prime}_{1}\in C_{2}$ .
$\blacksquare$

If the length of $P$ is even, then $v^{\prime}_{1}\in C_{1}$ and $v^{\prime}_{2}\in C_{2}$ .

Figure 9: The two paths in

\mathscr{VD}

formed by the endpoints of the path in

\mathscr{ED}

.

Proof.

This can be easily verified by observing that when two pieces share a side and come into contact, the clockwise-next corner on one piece corresponds to the counterclockwise-next corner on the other(Figure 9). $\hfill\blacktriangleleft$ In addition, Lemma 10 leads to the following lemma, which helps to simplify our proof:

Lemma 11.

Let $e$ and $e^{\prime}$ be boundary edges of $G^{X}$ such that they share an endpoint $v$ . If $e$ and $e^{\prime}$ are connected by a path in $\mathscr{ED}$ , the connected component of $\mathscr{VD}$ that includes $v$ contains a cycle.

Proof.

By Lemma 10, if $e$ and $e^{\prime}$ are connected by a path in $\mathscr{ED}$ , we can trace a path in $\mathscr{VD}$ that begins and ends at $v$ (Figure 10). This implies that the component containing $v$ includes a cycle. $\hfill\blacktriangleleft$

Figure 10: Illustration of cases where two edges on the boundary of

X

, either sharing a vertex of

X

(left) or a point on an edge (right), become the endpoints of a path in

\mathscr{ED}

.

In particular, we use these lemmas in combination as follows:

Lemma 12.

Let $C$ be a connected component of $\mathscr{VD}$ that contains a boundary node $v$ , and suppose the following conditions hold:

$\blacksquare$

Both of the next sides $s$ and $s^{\prime}$ of $v$ along the boundary correspond to monochromatic nodes in $\mathscr{ED}$ .
$\blacksquare$

None of the next sides of any other node in $C$ correspond to monochromatic nodes in $\mathscr{ED}$ .

Then $C$ forms a cycle.

4 Proof Overview and Example

In this section, we provide an overview of how to prove the impossibility. We let $P$ be a square $S$ and $P^{\prime}$ be an equilateral triangle $T$ . We denote the side Euclidean lengths of $S$ and $T$ by $\sigma$ and $\tau$ , respectively, and set $\sigma=\sqrt{\sqrt{3}}$ and $\tau=2$ so that both areas are $\sqrt{3}$ .

First, in Section 5.1, we consider the equivalence classes of the cut graph under the equivalence relation $\sim$ . Although this is essentially a brute-force exhaustive search, several tools are introduced to help to reduce the number of case distinctions. Next, in Section 5.2, we perform a more detailed analysis of the properties that hold for matching diagrams when considering equilateral triangles and squares. Finally, in Section 5.3, using these tools, we complete the proof by deriving contradictions for each individual case.

In the following, we present an example of the proof method by borrowing some tools in advance. We focus on the case where representative elements of equivalence classes $G^{T}$ and $G^{S}$ are the cut graphs shown on the left of Figure 11. This pair of cut graphs corresponds to ${G^{T}_{\mathfrak{D}1}}$ and ${G^{S}_{\mathfrak{A}3}}$ in the later labeling. the same proof also applies to ${G^{T}_{\mathfrak{D}1}}$ and ${G^{S}_{\mathfrak{D}7}}$ .

Figure 11: The pair of

{G^{T}_{\mathfrak{D}1}}

and

{G^{S}_{\mathfrak{A}3}}

, the tree

Y

contained in their

\mathscr{VD}

, and the possible combinations of side edge lengths of

T

.

Lemma 13.

The combination of ${G^{T}_{\mathfrak{D}1}}$ and ${G^{S}_{\mathfrak{A}3}}$ is infeasible.

Proof.

In this case, by Lemma 21, which will be given later, $\mathscr{VD}$ contains, as a connected component, a tree $Y$ that connects each corner of $T$ and a degree-3 vertex $q$ by a well-behaved path. Let $v_{x}$ , $v_{y}$ , and $v_{z}$ be the three leaves of $Y$ , with the adjacent sides of $v_{x}$ being $x_{1}$ and $x_{2}$ , those of $v_{y}$ being $y_{1}$ and $y_{2}$ , and those of $v_{z}$ being $z_{1}$ and $z_{2}$ (see the middle of Figure 11). Here, the sides $x_{1}$ , $x_{2}$ , $y_{1}$ , $y_{2}$ , $z_{1}$ , and $z_{2}$ can be grouped into three pairs, each pair forming a side of $T$ . Therefore, one of the following holds (see the right of Figure 11):

$\blacksquare$

Equation 1: $\|x_{1}\|+\|y_{2}\|=\|y_{1}\|+\|z_{2}\|=\|z_{1}\|+\|x_{2}\|=\tau$ .
$\blacksquare$

Equation 2: $\|x_{1}\|+\|z_{2}\|=\|y_{1}\|+\|x_{2}\|=\|z_{1}\|+\|y_{2}\|=\tau$ .

Let $W_{x}$ , $W_{y}$ , and $W_{z}$ be the paths in $\mathscr{VD}$ between each leaf and $q$ . We consider the number of points from $N^{T}_{\mathit{dit}}(\mathscr{VD})$ and $N^{S}_{\mathit{dit}}(\mathscr{VD})$ included in each $W_{-}$ . Since the vertices $v_{x}$ , $v_{y}$ , $v_{z}$ , and the convex vertex $q$ are all included in $G^{T}$ , the weight of both endpoint nodes of each $W_{-}$ is at most $\pi$ . By Observation 6, each $W_{-}$ contains at least one node of $N^{S}_{\mathit{dit}}(\mathscr{VD})$ . Moreover, since the weight of a divide-in-two vertex is $\pi$ , the elements of $N^{T}_{\mathit{dit}}(\mathscr{VD})$ appear alternately with those of $N^{S}_{\mathit{dit}}(\mathscr{VD})$ , and the number of $N^{T}_{\mathit{dit}}(\mathscr{VD})$ contained is one less than the number of $N^{S}_{\mathit{dit}}(\mathscr{VD})$ . Therefore, since $\|N^{S}_{\mathit{dit}}(\mathscr{VD})\|=4$ , the number of elements from $N^{S}_{\mathit{dit}}(\mathscr{VD})$ in each path is $1$ or $2$ , and the number from $N^{T}_{\mathit{dit}}(\mathscr{VD})$ is $0$ or $1$ . If $Y$ includes a point in $N^{T}_{\mathit{dit}}(\mathscr{VD})$ , it is a side vertex of $G^{T}$ .

If $Y$ includes exactly one side vertex $t$ , then the only monochromatic sides connected to $Y$ are the two adjacent to $t$ . Therefore, the connected component including $t$ must contain a cycle by Lemma 12, contradicting the fact that $Y$ is a tree.

Next, we consider the case where $Y$ includes no side vertex of $T$ . In this case, there are two possible structures for $Y$ , as shown in Figure 12. Depending on whether we are considering the left or right case in Figure 12, by Lemma 9, we have one of the following:

$\blacksquare$

Equations A: $\|x_{1}\|+\|y_{2}\|=\sigma$ , $\|y_{1}\|+\|z_{2}\|=\sigma$ , $\|z_{1}\|+\|x_{2}\|=\sigma$ .
$\blacksquare$

Equations B: $\|x_{1}\|=\|y_{2}\|$ , $\|y_{1}\|=\|z_{2}\|$ , $\|z_{1}\|+\|x_{2}\|=\sigma$ .

Here, even if $Y$ contains a flat node, by Lemma 20, which will be shown later, the Euclidean length of the side of the piece being divided is $\sigma$ .

From Equations A and Equation 1 or 2, we derive $\|x_{1}\|+\|x_{2}\|+\|y_{1}\|+\|y_{2}\|+\|z_{1}\|+\|z_{2}\|=3\sigma=3\tau,$ which contradicts $\sigma\neq\tau$ . From Equations B and Equation 1, we have $\|z_{1}\|+\|x_{2}\|=\sigma$ and $\|z_{1}\|+\|x_{2}\|=\tau$ , which is a contradiction. From Equations B and Equation 2, we have $\|z_{1}\|+\|y_{2}\|=\sigma$ and $\|z_{1}\|+\|y_{2}\|=\tau$ , which is also a contradiction.

Figure 12: The possible structures for

Y

.

$\hfill\blacktriangleleft$

5 Main Proof

In this section, we give the proof of Theorem 1.

5.1 Enumeration of Patterns of Cut Graphs

In this section, we enumerate the equivalence classes of the equivalence relation $\sim$ . Before the enumeration, we present several geometric lemmas.

5.1.1 Geometric Lemma for Cut Graphs

Lemma 14.

In any dissection of $T$ and $S$ , no piece contains two corners of $T$ . Thus, the number of pieces must be at least $3$ , and in a three-piece dissection $P_{1},P_{2},P_{3}$ , each $P_{i}$ contains exactly one corner of $T$ .

Proof.

Suppose a piece contains two corners of $T$ , whose Euclidean distance is $\tau=2$ . The longest distance between any two points in $S$ is $\sqrt{2\sqrt{3}}$ , so no piece contains points that are farther apart than this distance. Since $\sqrt{2\sqrt{3}}<2$ , we obtain a contradiction. $\hfill\blacktriangleleft$

Lemma 15.

Let $P_{1},P_{2},P_{3}$ be a three-piece dissection of $T$ and $S$ . Then no $P_{i}$ contains two diagonal corners of $S$ .

Proof.

If a single piece $P_{i}$ contains the diagonal corners of $S$ , the diameter of $P_{i}$ is $\sqrt{2\sqrt{3}}$ . Placing a line segment $d$ of this Euclidean length $\sqrt{2\sqrt{3}}$ in $T$ requires its endpoints to reside within the region in $T$ bounded by the two blue parallel lines shown in Figure 13. By Lemma 14, piece $P_{i}$ must also include exactly one corner $v$ of $T$ . Since the line segment $d$ must be a diameter of $P_{i}$ , $d$ must in fact have $v$ as an endpoint. Limited by the region, $d$ must form an angle of more than $\frac{\pi}{4}$ with an edge of $T$ (the horizontal edge in Figure 13). However in $S$ , the diagonal has only $\frac{\pi}{4}$ of material on either side of its endpoints. Thus, $P_{i}$ cannot fully cover the corner $v$ of $T$ , i.e., $v$ is in fact cut. This contradicts Lemma 14. $\hfill\blacktriangleleft$

Figure 13: Ways to place a line segment of Euclidean length

\sqrt{2\sqrt{3}}

, the diagonal of

S

, in

T

.

Lemma 16.

Let $P_{1},P_{2},P_{3}$ be a three-piece dissection of $T$ and $S$ . Then we can assume without loss of generality that each $P_{i}$ is a simple polygon.

Proof.

By Lemmas 14 and 15, the boundary of each polygon must be cut at least twice. Thus, under the assumption of a three-piece dissection, the number of holes in a single piece is at most one, and its interior must be filled by exactly one other piece. In this case (right of Figure 14), we can remove the cycle to obtain a dissection with fewer pieces. Similarly, if the dissection includes cut lines whose endpoints are internal (left of Figure 14), we can remove these cuts while maintaining the same number of pieces. Thus, in either case, we obtain a dissection with the same or smaller number of pieces that are all simple. $\hfill\blacktriangleleft$

Figure 14: After removing cut lines that create non-simple polygons, the obtained dissection has the same or fewer number of pieces.

5.1.2 Procedure for Enumerating Cut Graphs

We classify the possible equivalence classes of the relation $\sim$ using Lemmas 14, 15, and 16.

We begin by abstracting the boundary of the target shape as a disk, ignoring differences in vertex types. First, consider the case of partitioning the disk into two pieces. Since each piece must be a simple polygon (by Lemma 16), the boundary must be cut at least once. As shown on the left of Figure 16, there is a unique way to perform such a cut: connect two points on the circular boundary with a cut line $C$ . The resulting boundary of the pieces consists of three types of segments: parts from the cut line $C$ , parts from the original boundary, and two switching points between them.

To obtain three pieces, we make a second cut $C^{\prime}$ on one of the two pieces, again connecting two boundary points. As shown on the right of Figure 16, there are exactly six distinct ways to make such a second cut. These yield six topologically distinct configurations, which we enumerate explicitly in Figure 16 and label as Type $\mathfrak{A}$ through Type $\mathfrak{F}$ .

Figure 15: Left: The unique configuration for the first cut of the disk and the resulting boundary structure. Right: The six possible configurations for the second cut.

Figure 16: The topological classification of cut graphs when the boundary is abstracted.

We now apply this abstract classification to the actual dissection of the target shapes $S$ and $T$ . To do so, we must account for how the endpoints of each cut line attach to the corners or sides of the target shape, as well as the presence of vertices of degree three or higher. Using Lemma 14, we enumerate the equivalence classes of $G^{T}$ as shown in Figure 17, denoting them as $G^{T}_{i}$ .

Figure 17: The possible equivalence classes of

G^{T}

. Open circles represent possible paths of degree-2 vertices from subdivision.

G^{T}_{\mathfrak{D}1}

,

G^{T}_{\mathfrak{D}2}

, and

G^{T}_{\mathfrak{D}3}

have a degree-3 vertex of type 4, 6 (flat), and 5, respectively.

Similarly, applying Lemma 15, we enumerate the equivalence classes of $G^{S}$ as shown in Figures 18 and 19, denoted as $G^{S}_{j}$ .

Figure 18: The possible equivalence classes of

G^{S}

: Types

\mathfrak{A}

,

\mathfrak{B}

,

\mathfrak{C}

, and

\mathfrak{D}

.

Figure 19: The possible equivalence classes of

G^{S}

: Types

\mathfrak{E}

and

\mathfrak{F}

.

To identify feasible pairings between $G^{S}_{-}$ and $G^{T}_{-}$ , we introduce the following angular invariant:

Definition 17.

For a graph $G^{X}$ and an angle $\theta<\pi$ , the $\theta$ -diff is defined as the number of times $\theta$ appears minus the number of times $2\pi-\theta$ appears as an interior angle. We define cc-diff as the sum of all $\theta$ -diffs for $\theta<\pi$ , and tri-diff as the difference $\pi/3$ -diff $-\,2\pi/3$ -diff.

Since $\theta$ -diff is preserved under subdivision, the cc-diff of each $G^{T}_{i}$ and $G^{S}_{j}$ can be determined by counting convex minus reflex angles at solid vertices in Figures 17, 18, and 19:

$\blacksquare$

The value of cc-diff is $12$ for $G^{T}_{\mathfrak{D}1}$ , $11$ for each of $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}$ , and $10$ for each of $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}$ .
$\blacksquare$
The value of cc-diff is
- –
  
  $14$ for $G^{S}_{\mathfrak{A}1}$ ,
- –
  
  $13$ for each of $\{G^{S}_{\mathfrak{A}2},G^{S}_{\mathfrak{D}1},G^{S}_{\mathfrak{D}2}\}$ ,
- –
  
  $12$ for each of $\{G^{S}_{\mathfrak{A}3},G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1},G^{S}_{% \mathfrak{D}3},G^{S}_{\mathfrak{D}4},G^{S}_{\mathfrak{D}6},G^{S}_{\mathfrak{D}% 7},G^{S}_{\mathfrak{F}1},G^{S}_{\mathfrak{F}2},G^{S}_{\mathfrak{F}3},G^{S}_{% \mathfrak{F}4},G^{S}_{\mathfrak{F}11}\}$ ,
- –
  
  $11$ for each of $\{G^{S}_{\mathfrak{A}5},G^{S}_{\mathfrak{B}2},G^{S}_{\mathfrak{D}5},G^{S}_{% \mathfrak{D}8},G^{S}_{\mathfrak{D}9},G^{S}_{\mathfrak{D}11},G^{S}_{\mathfrak{D% }12},G^{S}_{\mathfrak{E}1},G^{S}_{\mathfrak{E}2},G^{S}_{\mathfrak{E}3},G^{S}_{% \mathfrak{E}4},G^{S}_{\mathfrak{F}5},G^{S}_{\mathfrak{F}6},$ $G^{S}_{\mathfrak{F}7},G^{S}_{\mathfrak{F}9}\}$ ,
- –
  
  $10$ for each of $\{G^{S}_{\mathfrak{A}6},G^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1},G^{S}_{% \mathfrak{D}10},G^{S}_{\mathfrak{D}13},G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak% {E}5},G^{S}_{\mathfrak{E}6},G^{S}_{\mathfrak{E}7},G^{S}_{\mathfrak{F}8},G^{S}_% {\mathfrak{F}10}\}$ , and
- –
  
  $9$ for each of $\{G^{S}_{\mathfrak{D}15},G^{S}_{\mathfrak{E}8}\}$ .

Moreover, tri-diff can be computed as at least $3$ for each of $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}$ and less than $3$ for each of $\{G^{S}_{\mathfrak{A}5},\allowbreak G^{S}_{\mathfrak{D}8},\allowbreak G^{S}_{% \mathfrak{D}9},\allowbreak G^{S}_{\mathfrak{D}11},\allowbreak G^{S}_{\mathfrak% {D}12},\allowbreak G^{S}_{\mathfrak{F}5},G^{S}_{\mathfrak{F}6},\allowbreak G^{% S}_{\mathfrak{F}7},\allowbreak G^{S}_{\mathfrak{F}9}\}$ .

In order to generate the same set of pieces by $G^{S}$ and $G^{T}$ , $\theta$ -diff must match between them for every $\theta<\pi$ . Therefore, only the following combinations can be feasible, where $\{G^{T}_{i},\ldots\}\times\{G^{S}_{j},\ldots\}$ denotes the set of all pairwise combinations of $G^{T}_{i}$ and $G^{S}_{j}$ :

$\blacksquare$

$\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}3},G^{S}_{\mathfrak{A}4},G% ^{S}_{\mathfrak{B}1},G^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4},G^{S}_{% \mathfrak{D}6},G^{S}_{\mathfrak{D}7},G^{S}_{\mathfrak{F}1},G^{S}_{\mathfrak{F}% 2},G^{S}_{\mathfrak{F}3},G^{S}_{\mathfrak{F}4},G^{S}_{\mathfrak{F}11}\}$ ,
$\blacksquare$

$\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{B}2},G% ^{S}_{\mathfrak{D}5},G^{S}_{\mathfrak{E}1},G^{S}_{\mathfrak{E}2},G^{S}_{% \mathfrak{E}3},G^{S}_{\mathfrak{E}4}\}$ ,
$\blacksquare$

$\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},G% ^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1},G^{S}_{\mathfrak{D}10},G^{S}_{% \mathfrak{D}13},G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak{E}5},G^{S}_{\mathfrak{% E}6},G^{S}_{\mathfrak{E}7},G^{S}_{\mathfrak{F}8},G^{S}_{\mathfrak{F}10}\}$ .

5.2 Lemmas for Equilateral Triangle and Square

In this section, we present two lemmas that are useful in proving properties related to the dissection between an equilateral triangle and a square.

The first lemma constrains on the structure of the connected components of $\mathscr{VD}$ and can be described as follows:

Lemma 18.

Any connected component of $\mathscr{VD}$ includes either all corner vertices of $T$ or none, and includes an even number of corner vertices of $S$ .

Proof.

Except for the corner vertices of $S$ and $T$ , the weight of any vertex is a multiple of $\pi$ (see Figure 20). Therefore, if the conditions in the statement do not hold, the sums on both sides will not match. It contradicts to Observation 6. $\hfill\blacktriangleleft$

Figure 20: A connected component of

\mathscr{VD}

and the sum of interior angles within it.

The second lemma is used to handle well-behavior properties. When dealing with the 3-piece dissection between an equilateral triangle and a square, a path ceases to be well-behaved when it passes through a corner vertex, a vertex adjacent to a flat vertex, or a side vertex located on a trisected edge of the target shape. Here, in addition to the node in $\mathscr{ED}$ added for an edge containing a flat node, we also define the node corresponding to the middle of a trisected side as a trisected-mid node. Thus, to verify that a path is well-behaved, it is sufficient to check that it does not pass through a corner vertex and does not go through the endpoints of a flat node or a trisected-mid node. Regarding the behavior of flat nodes and trisected-mid nodes in $\mathscr{ED}$ , the following holds:

Definition 19.

Let $e$ be a boundary edge of $G^{S}$ and $v,v^{\prime}$ be the adjacent vertices of $x$ . $(v,e,v^{\prime})$ is called a U-shaped boundary if both $v$ and $v^{\prime}$ are a corner vertex of degree 1 in $\mathscr{VD}$ .

Lemma 20.

Assume that $(v,e,v^{\prime})$ forms a U-shaped boundary and that the connected components containing $v$ and $v^{\prime}$ (which may be the same) are both simple paths. Then, the other end node $e^{\prime}$ of the path in $\mathscr{ED}$ with $e$ as an end node is either a flat node or a trisected-mid node in $\mathscr{ED}$ .

Proof.

Let $W=(v,v_{1},\ldots,v_{k})$ and $W^{\prime}=(v^{\prime},v^{\prime}_{1},\ldots,v^{\prime}_{k^{\prime}})$ be the paths in $\mathscr{VD}$ beginning from $v$ and $v^{\prime}$ , respectively.

First, we show that for each of the sequences $v_{1},\ldots,v_{k-1}$ and $v^{\prime}_{1},\ldots,v^{\prime}_{k^{\prime}-1}$ , at least one element in each sequence is either a flat vertex or a boundary vertex of $S$ or $T$ . It suffices to show this for $v_{1},\ldots,v_{k-1}$ . Suppose, for contradiction, that all $v_{1},\ldots,v_{k-1}$ are paired vertices. Then, by Lemma 5, $\angle{v_{k}}$ would be either $\pi/2$ or $3\pi/2$ , depending on whether $v_{k}\in N^{T}(\mathscr{VD})$ or $v_{k}\in N^{S}(\mathscr{VD})$ . However, since $v_{k}$ is an endpoint of the path, it must be a corner vertex of $X\in\{S,T\}$ . In the case of $T$ , the internal angle at $v_{k}$ would be $\pi/3$ , and in the case of $S$ , it would be $\pi/2$ , leading to a contradiction.

Therefore, both $v_{1},\ldots,v_{k-1}$ and $v^{\prime}_{1},\ldots,v^{\prime}_{k^{\prime}-1}$ must contain at least one flat vertex or boundary vertex of $S$ or $T$ . Let $s$ and $s^{\prime}$ be the first such points encountered along $W$ and $W^{\prime}$ from $v$ and $v^{\prime}$ , respectively. By Lemma 5, both $s$ and $s^{\prime}$ must belong to $N^{T}(\mathscr{VD})$ . Now, assume for contradiction that the statement of the lemma does not hold. Suppose that $e^{\prime}$ is neither a flat node nor trisected-mid node. Then, $e^{\prime}$ cannot have $s$ (or $s^{\prime}$ ) as its adjacent side. If it did, the other endpoint of $e^{\prime}$ would be a corner $t$ of $T$ , and $t$ and $s^{\prime}$ (or $s$ ) would be connected in $\mathscr{VD}$ , which contradicts the fact that $W^{\prime}$ (or $W$ ) is a path and Lemma 18. Therefore, at both $s$ and $s^{\prime}$ , the path in $\mathscr{ED}$ starting from $e$ has degree-2 and corresponds to cut lines of Euclidean length $\sigma$ perpendicular to a side of $S$ at both $s$ and $s^{\prime}$ . If the cut lines attached to $s$ and $s^{\prime}$ are the same, this would imply that $T$ has a pair of parallel sides on its boundary (right of Figure 21), leading to a contradiction. On the other hand, if the cut lines attached to $s$ and $s^{\prime}$ are different, this implies the existence of a pair of cut lines of Euclidean length $\sigma$ orthogonal to the sides of $T$ , which intersect within $T$ (left of Figure 21), leading to another contradiction.

In the case where $W$ and $W^{\prime}$ are the same path, it is possible that $s$ and $s^{\prime}$ are the same vertex. However, this would mean that the endpoint of the path in $\mathscr{ED}$ that starts at $e$ would be $e$ itself, contradicting the definition of a path. $\hfill\blacktriangleleft$

Figure 21: Illustration of when the cut lines attached to

s

and

s^{\prime}

are the same (left) and different (right).

5.3 Proofs for Individual Cases

In this section, we apply the approach to eliminate the remaining cases narrowed down in Section 5.1. Rather than deriving a classification from abstract principles, we arrived at a practical case division through extensive trial-and-error analysis of all surviving cut graphs. Based on recurring structural features, we group the configurations into three representative types, which we refer to as Cases A, B, and C. Each of these captures a common geometric obstruction, and together they account for all infeasible instances identified in the enumeration. We begin by formulating Lemma 21 that justifies this trichotomy.

Lemma 21.

We define Cases A, B, and C as follows:

$\blacksquare$

Case A: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}6},G^{S}_{\mathfrak{F}1},G% ^{S}_{\mathfrak{F}2},G^{S}_{\mathfrak{F}4},G^{S}_{\mathfrak{F}11},G^{S}_{% \mathfrak{F}3}\}$ , $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{B}2}.G% ^{S}_{\mathfrak{E}1},G^{S}_{\mathfrak{E}3}\}$ , $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{F}8}\}$
$\blacksquare$

Case B: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}3},G^{S}_{\mathfrak{D}7}\}$ , $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{E}2},G% ^{S}_{\mathfrak{E}4}\}$
$\blacksquare$

Case C: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1},G% ^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4}\}$ , $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}$ , $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},% \allowbreak G^{S}_{\mathfrak{B}3},\allowbreak G^{S}_{\mathfrak{C}1},% \allowbreak G^{S}_{\mathfrak{D}10},\allowbreak G^{S}_{\mathfrak{D}13},% \allowbreak G^{S}_{\mathfrak{D}14},\allowbreak G^{S}_{\mathfrak{E}5},G^{S}_{% \mathfrak{E}6},\allowbreak G^{S}_{\mathfrak{E}7},G^{S}_{\mathfrak{F}10}\}$

Figure 22: The combinations of cut line graphs in Case A.

Figure 23: The combinations of cut line graphs in Case B.

Figure 24: The combinations of cut line graphs in Case C.

In Case A (Figure 22), the number of flat edges and the middle of trisected edges of $S$ or $T$ is less than the number of U-shaped boundaries. In Case B (Figure 23), there exists a well-behaved tree $Y$ of $\mathscr{ED}$ that connects a degree- $3$ vertex and each corners of $T$ by a well-behaved path. In Case C (Figure 24), there exists a well-behaved path $W$ that connects vertices of $S$ .

Proof.

In Case A, the statement clearly holds.

In Case B, by Lemma 18, the connected components of $\mathscr{VD}$ consist of a tree $Y$ connecting the corners of $T$ and paths $W_{1}$ and $W_{2}$ connecting the corners of $S$ , since there is a single vertex of degree 3 of $G^{S}$ and $G^{T}$ . According to Lemma 20, the paths in $\mathscr{ED}$ starting from the edges of the U-shaped boundary have either a flat node or a trisected-mid node as an endpoint. Thus, the adjacent vertices belong to either $W_{1}$ or $W_{2}$ . Consequently, all three paths composing $Y$ are well-behaved.

In Case C, there are at most three vertices of degree 3 in $\mathscr{VD}$ , and the number of leaves in a connected component is at most five. Therefore, by Lemma 18, $\mathscr{VD}$ must include a connected component that forms a path $W$ connecting a pair of corners of $S$ . It is clear that $W$ is well-behaved in the combinations $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1},G% ^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4}\}$ and $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},G% ^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1},G^{S}_{\mathfrak{D}13},G^{S}_{% \mathfrak{D}14},G^{S}_{\mathfrak{E}5},G^{S}_{\mathfrak{E}6},G^{S}_{\mathfrak{E% }7}\}$ , since by Observation 5, $W$ does not pass through corner vertices of $S$ with degree greater than two. Now, we consider the remaining cases of $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}$ and $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10},% G^{S}_{\mathfrak{F}10}\}$ . Let $e$ be the side of $S$ whose both corners have degree greater than 2 in $\mathscr{VD}$ . Since $e$ is monochromatic, any edge $e^{\prime}$ sharing a path with $e$ in $\mathscr{ED}$ is also monochromatic. If $e^{\prime}$ is a flat node or a trisected-mid node, $W$ does not pass through these endpoints, making it well-behaved. If $e^{\prime}$ is an edge bisecting an side of $T$ , then any edge $e^{\prime\prime}$ sharing this edge with $e^{\prime}$ is also monochromatic. By following paths in $\mathscr{ED}$ recursively, we eventually reach a flat node or a trisected-mid node, which is also monochromatic. Thus, $W$ does not pass through these vertices, making it well-behaved. $\hfill\blacktriangleleft$

The structural property established in the above lemma allows us to rule out each of the remaining cases. We now examine them one by one.

Lemma 22.

Case A is infeasible.

Proof.

Each Case A pattern contains a single vertex of degree 3, and the three corners of $T$ are connected by a tree $Y$ that includes this degree-3 vertex. Therefore, the corners of $S$ on the U-shaped boundary $(v,e,v^{\prime})$ are both included in paths of $\mathscr{VD}$ .

By Lemma 20, the other endpoint of the path in $\mathscr{ED}$ starting from $e$ must be either a flat node or a trisected-mid node. Furthermore, by Lemma 21, the number of such edges is smaller than the number of U-shaped boundaries. This leads to a contradiction, proving that Case A is infeasible. $\hfill\blacktriangleleft$

Lemma 23.

Case B is infeasible.

Proof.

In this case, there exists a well-behaved tree $Y$ by Lemma 21. Let $W_{x}$ , $W_{y}$ , and $W_{z}$ be the paths in $\mathscr{VD}$ between each leaf and $q$ . Let $v_{x}$ , $v_{y}$ , and $v_{z}$ be the three leaves of $Y$ with the sides next to $v_{x}$ being $x_{1}$ and $x_{2}$ , those connected to $v_{y}$ being $y_{1}$ and $y_{2}$ , and those connected to $v_{z}$ being $z_{1}$ and $z_{2}$ . Here, the sides $x_{1}$ , $x_{2}$ , $y_{1}$ , $y_{2}$ , $z_{1}$ , and $z_{2}$ can be grouped into three pairs, each pair forming a side of $T$ .

Therefore, one of the following holds (see the left of Figure 11):

$\blacksquare$

Equation 1: $x_{1}+y_{2}=y_{1}+z_{2}=z_{1}+x_{2}=\tau$ .
$\blacksquare$

Equation 2: $x_{1}+z_{2}=y_{1}+x_{2}=z_{1}+y_{2}=\tau$ .

We now consider two cases based on the location of the degree-3 vertex $q$ of $Y$ : in Case B-1, $q$ belongs to $G^{T}$ , while in Case B-2, it belongs to $G^{S}$ .

Case B-1: The degree-3 vertex $q$ is in $G^{T}$ .: This proof is given at Section 4.
Case B-2: The degree-3 vertex $q$ is in $G^{S}$ .: This part can also be proved similarly to Section 4, so we omit it.

$\hfill\blacktriangleleft$

Lemma 24.

Case C is infeasible.

Proof.

We classify the cases as follows:

$\blacksquare$

Case C-1: $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}% ,G^{S}_{\mathfrak{F}10}\}$
$\blacksquare$

Case C-2: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},% G^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1}\}$
$\blacksquare$

Case C-3: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13}% ,G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak{E}5},G^{S}_{\mathfrak{E}6},G^{S}_{% \mathfrak{E}7}\}$

By Lemmas 21 and 18, the structure of the connected components in each case can be classified as follows:

$\blacksquare$
Case C-1:
- –
  
  A well-behaved path $W$ and a tree $Y$ with a degree-3 vertex.
$\blacksquare$
Case C-2:
- –
  
  A well-behaved path $W_{1}$ , a path $W_{2}$ , and some component $C$ , or
- –
  
  A well-behaved path $W_{1}$ and some component $C$ .
$\blacksquare$
Case C-3:
- –
  
  A well-behaved path $W$ , a tadpole graph $L$ , which is a graph obtained by joining a cycle graph to a path graph with a bridge of degree 3, and a tree $Y$ with a degree-3 vertex, or
- –
  
  A well-behaved path $W$ and a tree $Y$ with a degree-4 vertex.

Case C-1: $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}% ,G^{S}_{\mathfrak{F}10}\}$ .

As shown in the proof of Lemma 21, the node in $\mathscr{ED}$ that shares a path with the side of $S$ where both adjacent corners have degree-2 in $\mathscr{VD}$ must be either a trisected-mid node or a flat node. In $G^{S}_{\mathfrak{F}10}$ , the trisected-mid node lies on the side of $S$ , however its Euclidean length is strictly shorter than the side length of $S$ , leading to a contradiction. Thus, we only consider $G^{S}_{\mathfrak{D}5}$ and $G^{S}_{\mathfrak{D}10}$ . Since the endpoints $w$ and $w^{\prime}$ of $W$ are corner vertices of $S$ , if $W$ contains a divide-in-two vertex $t$ on the side of $S$ , only the two next sides of $t$ become monochromatic (Figure 25). This contradicts Lemma 12. Thus, we only consider the case where $W$ does not contain a divide-in-two vertex on the side of $S$ .

Figure 25: Case where

W

contains a divide-in-two vertex

t

on the side of

S

(left:

G^{S}_{\mathfrak{D}5}

, right:

G^{S}_{\mathfrak{D}10}

).

Case C-1-1: $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}$ .

Since $W$ does not contain a divide-in-two vertex on the side of $S$ , there is exactly one divide-in-two vertex on the side of $T$ contained in $W$ . Thus, the structure of $W$ must be one of the two cases shown in Figure 26. In these cases, one of the along sequences consists of a single path, while the other consists of two paths. According to Lemma 9, the sum of the Euclidean lengths of the paths in the along sequence consisting of two paths should equal $\tau$ . However, the Euclidean length of the counterclockwise-next side of $w$ and clockwise-next side of $w^{\prime}$ are both $\sigma$ , and the sum of the Euclidean lengths of the clockwise next side of $w$ and the counterclockwise next side of $w^{\prime}$ is also $\sigma$ . As a result, it is impossible for either sum to be $\tau$ , leading to a contradiction.

Figure 26: Possible structures in the case where

\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}

.

Case C-1-2: $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}\}$ .

Since $W$ does not contain a divide-in-two vertex on the side of $S$ , $W$ either contains only one divide-in-two vertex on the side of $T$ , or it contains one flat vertex on $S$ and two divide-in-two vertices on the side of $T$ . In the former case, a contradiction arises in the same way as in Case C-1-1. In the latter case, the remaining boundary vertex $t$ on $T$ that is not contained in $W$ is contained in $Y$ . (There is no divide-in-two vertex on $S$ that is not contained in $W$ , so $t$ cannot be part of a cycle.) Since $t$ is contained in $Y$ , only its next side becomes monochromatic, which contradicts Lemma 12 (Figure 27).

Figure 27: Possible structures in the case where

\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}\}

.

Case C-2: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},% G^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1}\}$ .

If $\mathscr{VD}$ has two separate paths $W_{1}$ and $W_{2}$ , a contradiction arises by Lemma 20. Therefore, we consider the case where there is only one path $W$ contained in $\mathscr{VD}$ . By Lemma 20, it suffices to consider the case where the endpoints $w$ and $w^{\prime}$ of $W$ belong to different U-shaped boundaries. There are two possibilities: either $w$ and $w^{\prime}$ are diagonal corners of $S$ , or $w$ and $w^{\prime}$ are the endpoint corners of a single side of $S$ .

Case C-2-1: the case where $𝒘$ and $w^{\prime}$ are diagonal corners of $𝑺$ .

If $W$ contains a divide-in-two node on the side of $S$ , it contradicts Lemma 12 (see the left of Figure 28). Conversely, if $W$ does not contain a divide-in-two node on the side of $S$ , the structure of $W$ must be one of the two cases shown in the right of Figure 28. In both cases, one of the along sequences of $W$ forms a single path in $\mathscr{ED}$ , however the next sides of $w$ and $w^{\prime}$ in different directions have different Euclidean lengths, leading to a contradiction to Observation 3.

Figure 28: Possible structures in the case where

w

and

w^{\prime}

are diagonal corners of

S

.

Case C-2-2: the case where $𝒘$ and $w^{\prime}$ are the endpoint corners of a single side of $𝑺$ .

If $W$ contains two divide-in-two nodes on $S$ , one of them divides the side whose endpoints are the corner vertices $w$ and $w^{\prime}$ . The boundary edges corresponding to the divided side are both monochromatic, which contradicts Lemma 12. For the other cases, where $W$ contains at most one divide-in-two node on $S$ , a contradiction arises in the same way as in Case C-1-2.

Case C-3: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13}% ,G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak{E}5},G^{S}_{\mathfrak{E}6},G^{S}_{% \mathfrak{E}7}\}$ .

If $\mathscr{VD}$ contains a tadpole graph $L$ , then the degree-2 corner vertex of $S$ (along with one of the degree-1 corner vertices) is included in $L$ , and the tree $Y$ is well-behaved. In this case, a contradiction arises using the same argument as in Case B. Therefore, we focus on the scenario where $\mathscr{VD}$ consists of a well-behaved path $W$ and a tree $Y$ with a degree-4 vertex. In each case, there exist two sides that are not divided by a side vertex, which we denote as $e$ and $e^{\prime}$ .

Case C-3-1: the case where $𝒆$ and $e^{\prime}$ are connected by a path in $\mathscr{ED}$ .

In the cases of $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}4}\},\{G^{T}_{\mathfrak{D}% 3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak{E}5}\}$ , Lemma 10 implies that a degree-2 corner vertex is included in a cycle, contradicting the fact that $\mathscr{VD}$ does not contain a tadpole graph. In other cases, such as $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3}\},\{G^{T}_{\mathfrak{D}% 3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13},G^{S}_{\mathfrak{E}6}% ,G^{S}_{\mathfrak{E}7}\}$ , computing the along sequence of $W$ on the side that is not $e$ , regardless of the number of divide-in-two vertices contained in $W$ , leads to a contradiction with Lemma 9.

Case C-3-2: the case where $𝒆$ and $e^{\prime}$ are not connected by a path in $\mathscr{ED}$ .

Since $e$ and $e^{\prime}$ both have a Euclidean length of $\sigma$ , the other endpoints of the $\mathscr{ED}$ paths originating from each of them must be different edges on the boundary of $T$ . Therefore, $W$ contains at least two divide-in-two vertices on the sides of $T$ and at least one divide-in-two vertex $t$ on the side of $S$ . Let the endpoints of $W$ be $w$ and $w^{\prime}$ . If $t$ shares a side on the boundary of $S$ with at least one of $w$ or $w^{\prime}$ , then the monochromatic edges whose endpoints are contained in $W$ must either exist in an odd number, exist in a pair with different orientations, or exist in a pair that shares an endpoint. In any case, this contradicts Lemma 12. Therefore, it is sufficient to consider the case where $t$ shares no side on the boundary of $S$ with $w$ and $w^{\prime}$ . This can occur in $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3}\}$ and $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13}\}$ , where the endpoints of $W$ are on a single side of $S$ , and $t$ is located on its opposite side (Figure 29). However, in this case, focusing on the remaining divide-in-two vertices on the side of $T$ leads to a contradiction for the same reason as in Case C-1-2. $\hfill\blacktriangleleft$

Figure 29: The case where

t

shares no side on the boundary of

S

with

w

and

w^{\prime}

. Left:

\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3}\}

; Right:

\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13}\}

.

6 Conclusion

In this paper, we demonstrated that a three-piece dissection between a square and an equilateral triangle does not exist. The concept of matching diagrams, which was central to our proof, seems to be broadly applicable as a method for analyzing dissections.

We believe that our approach can be extended to handle the case where pieces can be flipped over. The challenge is to do so without vastly increasing the number of cases that need to be considered. We highlight this and other open problems:

$\blacksquare$

Is a three-piece dissection still impossible if flipping is allowed?
$\blacksquare$

Is a three-piece dissection still impossible if we allow nonpolygonal (curved) pieces?
$\blacksquare$

Are there only a finite number of rectangles that can be dissected into three pieces from a triangle? If so, how can they be enumerated?
$\blacksquare$

Are there any other four-piece dissections between an equilateral triangle and a square, aside from Figure 1?
$\blacksquare$

Are there any pairs of regular $n$ -gons and $m$ -gons that can be dissected into three pieces, where $n\neq m$ ?

References

[1] Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, and Scott D. Kominers. Hinged dissections exist. In Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG ’08, pages 110–119, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1377676.1377695.
[2] Farkas Bolyai. Tentamen juventutem studiosam in elementa matheseos purae, elementaris ac sublimioris, methodo intuitiva, evidentiaque huic propria, introducendi. Typis Collegii Refomatorum per Josephum et Simeonem Kali, Maros Vásárhely, 1832–1833.
[3] Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee. Dissection with the fewest pieces is hard, even to approximate. In Jin Akiyama, Hiro Ito, Toshinori Sakai, and Yushi Uno, editors, Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science, pages 37–48, 2016. doi:10.1007/978-3-319-48532-4_4.
[4] M. J. Cohn. Economical triangle-square dissection. Geometriae Dedicata, 3(4):447–467, February 1975. doi:10.1007/BF00181377.
[5] H. E. Dudeney. Puzzles and Prizes. Weekly Dispatch, 1902. April 6, April 20, May 4.
[6] Henry Ernest Dudeney. The Canterbury Puzzles and Other Curious Problems. E. P. Dutton and Company, New York, 1908.
[7] Henry Ernest Dudeney. Amusements in Mathematics. Thomas Nelson and Sons, London, 1917.
[8] Dania El-Khechen, John Iacono, and Thomas G. Fevens. Partitioning a polygon into two mirror congruent pieces. In Proceedings of the 20th Canadian Conference on Computational Geometry, 2008. URL: https://cccg.ca/proceedings/2008/paper32full.pdf.
[9] Greg N. Frederickson. Dissections: Plane and Fancy. Cambridge University Press, November 1997.
[10] Greg N. Frederickson. Hinged Dissections: Swinging & Twisting. Cambridge University Press, August 2002.
[11] Martin Gardner. Henry Ernest Dudeney: England’s greatest puzzlist. In The Second Scientific American Book of Mathematical Puzzles and Diversions, chapter 3. The University of Chicago Press, Chicago, 1961.
[12] Martin Gardner. Geometric dissections. In The Unexpected Hanging and Other Mathematical Diversions, chapter 4. The University of Chicago Press, Chicago, 1969.
[13] P. Gerwien. Zerschneidung jeder beliebigen Anzahl von gleichen geradlinigen Figuren in dieselben Stücke. Journal für die reine und angewandte Mathematik (Crelle’s Journal), 10:228–234 and Taf. III, 1833.
[14] Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. Efficient regular polygon dissections. Geometriae Dedicata, 80:247–262, 2000.
[15] Harry Lindgren. Recreational Problems in Geometric Dissections and How to Solve Them. Dover Publications, Inc., 1972. Revised and enlarged by Greg Frederickson.
[16] Mr. Lowry. Solution to question 269, [proposed] by Mr. W. Wallace. In T. Leybourn, editor, Mathematical Repository, volume 3, part 1, pages 44–46. W. Glendinning, London, 1814.
[17] G. Rote. Some thoughts about decomposing a polygon into two congruent pieces. Unfinished Draft, June 1997. URL: https://page.mi.fu-berlin.de/rote/Papers/pdf/Decomposition+of+a+polytope+into+two+congruent+pieces.pdf.
[18] William Wallace, editor. Elements of Geometry. Bell & Bradfute, Edinburgh, 8th edition, 1831.

[bib.bib1] [1] Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, and Scott D. Kominers. Hinged dissections exist. In Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG ’08, pages 110–119, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1377676.1377695.

[bib.bib2] [2] Farkas Bolyai. Tentamen juventutem studiosam in elementa matheseos purae, elementaris ac sublimioris, methodo intuitiva, evidentiaque huic propria, introducendi. Typis Collegii Refomatorum per Josephum et Simeonem Kali, Maros Vásárhely, 1832–1833.

[bib.bib3] [3] Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee. Dissection with the fewest pieces is hard, even to approximate. In Jin Akiyama, Hiro Ito, Toshinori Sakai, and Yushi Uno, editors, Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science, pages 37–48, 2016. doi:10.1007/978-3-319-48532-4_4.

[bib.bib4] [4] M. J. Cohn. Economical triangle-square dissection. Geometriae Dedicata, 3(4):447–467, February 1975. doi:10.1007/BF00181377.

[bib.bib5] [5] H. E. Dudeney. Puzzles and Prizes. Weekly Dispatch, 1902. April 6, April 20, May 4.

[bib.bib6] [6] Henry Ernest Dudeney. The Canterbury Puzzles and Other Curious Problems. E. P. Dutton and Company, New York, 1908.

[bib.bib7] [7] Henry Ernest Dudeney. Amusements in Mathematics. Thomas Nelson and Sons, London, 1917.

[bib.bib8] [8] Dania El-Khechen, John Iacono, and Thomas G. Fevens. Partitioning a polygon into two mirror congruent pieces. In Proceedings of the 20th Canadian Conference on Computational Geometry, 2008. URL: https://cccg.ca/proceedings/2008/paper32full.pdf.

[bib.bib9] [9] Greg N. Frederickson. Dissections: Plane and Fancy. Cambridge University Press, November 1997.

[bib.bib10] [10] Greg N. Frederickson. Hinged Dissections: Swinging & Twisting. Cambridge University Press, August 2002.

[bib.bib11] [11] Martin Gardner. Henry Ernest Dudeney: England’s greatest puzzlist. In The Second Scientific American Book of Mathematical Puzzles and Diversions, chapter 3. The University of Chicago Press, Chicago, 1961.

[bib.bib12] [12] Martin Gardner. Geometric dissections. In The Unexpected Hanging and Other Mathematical Diversions, chapter 4. The University of Chicago Press, Chicago, 1969.

[bib.bib13] [13] P. Gerwien. Zerschneidung jeder beliebigen Anzahl von gleichen geradlinigen Figuren in dieselben Stücke. Journal für die reine und angewandte Mathematik (Crelle’s Journal), 10:228–234 and Taf. III, 1833.

[bib.bib14] [14] Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. Efficient regular polygon dissections. Geometriae Dedicata, 80:247–262, 2000.

[bib.bib15] [15] Harry Lindgren. Recreational Problems in Geometric Dissections and How to Solve Them. Dover Publications, Inc., 1972. Revised and enlarged by Greg Frederickson.

[bib.bib16] [16] Mr. Lowry. Solution to question 269, [proposed] by Mr. W. Wallace. In T. Leybourn, editor, Mathematical Repository, volume 3, part 1, pages 44–46. W. Glendinning, London, 1814.

[bib.bib17] [17] G. Rote. Some thoughts about decomposing a polygon into two congruent pieces. Unfinished Draft, June 1997. URL: https://page.mi.fu-berlin.de/rote/Papers/pdf/Decomposition+of+a+polytope+into+two+congruent+pieces.pdf.

[bib.bib18] [18] William Wallace, editor. Elements of Geometry. Bell & Bradfute, Edinburgh, 8th edition, 1831.

Dudeney’s Dissection Is Optimal

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Theorem 1.

Overview

2 Preliminaries

3 Matching Diagram

3.1 Edge Matching Diagram

Definition 2.

Observation 3.

3.2 Vertex Matching Diagram

Definition 4.

Observation 5.

Observation 6.

3.3 Relationship between Vertex and Edge Matching Diagrams

Lemma 7.

Proof.

Definition 8.

Lemma 9.

Proof.

3.4 Lemmas when Flipping is not Allowed

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

4 Proof Overview and Example

Lemma 13.

Proof.

5 Main Proof

5.1 Enumeration of Patterns of Cut Graphs

5.1.1 Geometric Lemma for Cut Graphs

Lemma 14.

Proof.

Lemma 15.

Proof.

Lemma 16.

Proof.

5.1.2 Procedure for Enumerating Cut Graphs

Definition 17.

5.2 Lemmas for Equilateral Triangle and Square

Lemma 18.

Proof.

Definition 19.

Lemma 20.

Proof.

5.3 Proofs for Individual Cases

Lemma 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Proof.

Lemma 24.

Proof.

Case C-1: {𝑮𝕯⁢𝟐𝑻,𝑮𝕱⁢𝟏𝑻}×{𝑮𝕯⁢𝟓𝑺},{𝑮𝕯⁢𝟑𝑻,𝑮𝕰⁢𝟏𝑻}×{𝑮𝕯⁢𝟏𝟎𝑺,𝑮𝕱⁢𝟏𝟎𝑺}.

Case C-1-1: {𝑮𝕯⁢𝟐𝑻,𝑮𝕱⁢𝟏𝑻}×{𝑮𝕯⁢𝟓𝑺}.

Case C-1-2: {𝑮𝕯⁢𝟑𝑻,𝑮𝕰⁢𝟏𝑻}×{𝑮𝕯⁢𝟏𝟎𝑺}.

Case C-2: {𝑮𝕯⁢𝟏𝑻}×{𝑮𝕬⁢𝟒𝑺,𝑮𝕭⁢𝟏𝑺},{𝑮𝕯⁢𝟑𝑻,𝑮𝕰⁢𝟏𝑻}×{𝑮𝕬⁢𝟔𝑺,𝑮𝕭⁢𝟑𝑺,𝑮𝕮⁢𝟏𝑺}.

Case C-2-1: the case where 𝒘 and 𝒘′ are diagonal corners of 𝑺.

Case C-2-2: the case where 𝒘 and 𝒘′ are the endpoint corners of a single side of 𝑺.

Case C-3: {𝑮𝕯⁢𝟏𝑻}×{𝑮𝕯⁢𝟑𝑺,𝑮𝕯⁢𝟒𝑺},{𝑮𝕯⁢𝟑𝑻,𝑮𝕰⁢𝟏𝑻}×{𝑮𝕯⁢𝟏𝟑𝑺,𝑮𝕯⁢𝟏𝟒𝑺,𝑮𝕰⁢𝟓𝑺,𝑮𝕰⁢𝟔𝑺,𝑮𝕰⁢𝟕𝑺}.

Case C-3-1: the case where 𝒆 and 𝒆′ are connected by a path in 𝓔⁢𝓓.

Case C-3-2: the case where 𝒆 and 𝒆′ are not connected by a path in 𝓔⁢𝓓.

6 Conclusion

References

Case C-1: $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}% ,G^{S}_{\mathfrak{F}10}\}$ .

Case C-1-1: $\{G^{T}_{\mathfrak{D}2},G^{T}_{\mathfrak{F}1}\}\times\{G^{S}_{\mathfrak{D}5}\}$ .

Case C-1-2: $\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}10}\}$ .

Case C-2: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{A}4},G^{S}_{\mathfrak{B}1}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{A}6},% G^{S}_{\mathfrak{B}3},G^{S}_{\mathfrak{C}1}\}$ .

Case C-2-1: the case where $𝒘$ and $w^{\prime}$ are diagonal corners of $𝑺$ .

Case C-2-2: the case where $𝒘$ and $w^{\prime}$ are the endpoint corners of a single side of $𝑺$ .

Case C-3: $\{G^{T}_{\mathfrak{D}1}\}\times\{G^{S}_{\mathfrak{D}3},G^{S}_{\mathfrak{D}4}\}% ,\{G^{T}_{\mathfrak{D}3},G^{T}_{\mathfrak{E}1}\}\times\{G^{S}_{\mathfrak{D}13}% ,G^{S}_{\mathfrak{D}14},G^{S}_{\mathfrak{E}5},G^{S}_{\mathfrak{E}6},G^{S}_{% \mathfrak{E}7}\}$ .

Case C-3-1: the case where $𝒆$ and $e^{\prime}$ are connected by a path in $\mathscr{ED}$ .

Case C-3-2: the case where $𝒆$ and $e^{\prime}$ are not connected by a path in $\mathscr{ED}$ .