A perfect tree is the joins it leaves out

The connected cranes of the 1797 Hiden Senbazuru Orikata are folded from a square slit into a grid, the cranes left joined at some of the lattice points where four of them meet. No odd grid holds a perfect tree proved that the joins of a perfect tree — the fewest that hold every crane in one piece, each join merging four pieces that were separate — all lie on one colour of the lattice’s checkerboard, which rules out every odd grid at its corners. On one colour its search finished: two, four, eight and sixteen by sixteen have exactly one perfect tree each, and ten, fourteen and twenty have none.

It could not say why ten, fourteen and twenty fail, and it set a target for the argument. On one colour of a ten-by-ten grid there are forty-one points, the rim forces sixteen, and a perfect tree keeps thirty-three, so it must cut exactly eight — and those eight must break every one of the colour’s twenty-four loops, three each, with nothing wasted. Showing that no eight points can do it would be the argument.

It can be shown, and the showing is short enough to print. The trick is to describe a perfect tree by the joins it leaves out rather than by the joins it keeps.

Loops, and what cutting one point does #

On the tree’s colour, two points are linked when they are diagonal neighbours — the two same-coloured corners of one crane. The earlier essay showed that the joins of a perfect tree, linked that way, form a tree. Take every point of the colour and every link at once and the result is not a tree but a lattice of small squares: each square of four links surrounds a point of the other colour, and it is a loop.

A perfect tree is this graph with some points removed. Removing a point takes away the point and the links it had, and if it had four links and no removed neighbour, it takes away one point and four links, which removes exactly three independent loops: a graph’s count of independent loops is its links less its points plus its pieces, and that drops by three. The count on ten by ten is sixty-four links less forty-one points plus one piece, which is twenty-four independent loops — the twenty-four squares. A tree has none. So a perfect tree needs exactly eight cuts, as the earlier target said, and it needs them to take three loops each.

The same arithmetic says something the target did not. The loops are always exactly three times the cuts a perfect tree needs, on every even grid: twelve and four on eight by eight, twenty-four and eight on ten, sixty and twenty on fourteen, eighty-four and twenty-eight on sixteen, a hundred and forty-four and forty-eight on twenty. It is not a coincidence of sizes; it is the floor $(n^2 - 1)/3$ read through Euler’s count. And it means that the “no loop” half of being a tree comes free. A set of cuts of the right size, no two of them neighbours, leaves a perfect tree exactly when what remains is in one piece. A leftover loop and a split into two pieces are the same failure seen from two sides, and checking one checks both.

Two small facts finish the translation. Two cuts that are neighbours would be the two same-coloured corners of one crane, and that crane would be held by nothing, so no two cuts are neighbours. And the point diagonally in from a corner of the sheet is the only link of the corner crane’s forced join, so cutting it would strand that join: those four points are never cut, and neither is any point on the rim’s forced ring, which which cranes can stay joined first used to pin the smallest grids.

A tree of merges #

Read on the loops rather than the points, a cut merges the four loops round it into one region, the outside of the sheet counting as a loop of its own for a point beside the rim. What remains of the graph is in one piece exactly when those merges make one tree, over every loop and the outside, with no two loops merged twice. That is a structure a search can build a piece at a time, and it can refuse a bad piece the moment it is placed: a cut whose four loops are not four separate regions already closes a loop and can never be part of a perfect tree.

The search takes, at each step, the loop not yet touched by any cut that has the fewest cuts still able to break it, and tries each of them. Every loop must lose at least one corner, since a perfect tree has no loop, so one of those cuts is in any perfect tree that extends the cuts made so far; a cut tried at a branch point is set aside for its later siblings, so each set of cuts is reached down exactly one branch. When every loop has been touched the search tries every cut still able to merge four separate regions. Nothing is refused that a perfect tree could contain, so an empty search is a proof, and its branches are the proof’s cases.

On eight by eight there are two.

The first loop the search meets, beside a corner, can be broken by one of two points. One choice leads, after three cuts, to a loop that has no cut left that would not either strand a join or close a loop. The other leads straight to four cuts round the middle point, which is the eight-by-eight tree. That the tree is unique was a measurement before; here it is two cases on a page.

Ten by ten, in seven cases #

The ten-by-ten grid has no perfect tree, and these seven cases are the whole of the reason. The search begins at the loop beside the top corner, which two points can break. Each choice forces a sequence of others, because the loops along each edge have only one or two cuts that would not strand a join, and after seven cuts every branch has reached one of two dead ends. In five of them a loop has lost every cut that could break it: each of its four corners is kept by force, a neighbour of a cut already made, a point whose four loops are no longer four separate regions, or a cut an earlier case has already tried. In the other two every loop has been touched with seven cuts, but the merges have made four regions rather than one, and a single eighth cut could join at most four regions only if they met at one point, which none do.

That is the argument the earlier essay asked for, though not in the form it expected. It asked which eight points could break twenty-four loops at three each and hoped for an inequality. The answer is a case analysis of seven branches, each seven cuts deep, which is less elegant and entirely checkable: each panel can be verified by hand against the loops around it.

It also shows where the difficulty sits. The five stranded loops are all in the bottom half of the grid, the half the search reaches last, and loop (8,5) — the middle loop of the row of loops next to the bottom rim — is the one stranded most often, in three of the seven. The rim’s forced ring settles the outside; the loops just inside it are where ten by ten runs out of room.

How big each proof is #

The same search runs on every even grid up to sixteen.

It reproduces every count the join-by-join search made: one perfect tree on four, eight and sixteen, none on ten and fourteen. The proofs grow quickly. Ten by ten is seven cases; fourteen by fourteen is 761, none of them a tree, which is finite and checkable by machine but not a page anybody would read; sixteen by sixteen is 28,775 cases with one tree among them. Twenty by twenty needs forty-eight cuts for its hundred and forty-four loops, and this search does not finish it in reasonable time; the join search that settled twenty remains the evidence there. The growth is the reason a list cannot be the final answer: from ten to fourteen the cases multiply by a hundred, from fourteen to sixteen by nearly forty, and each step adds only a few more cuts to place. A proof that scaled would have to say something the cases only exhibit.

The cross of cuts between four quarters #

The cut drawing makes the doubling construction visible in a way the joins did not.

Sixteen’s one perfect tree cuts twenty-eight points. Sixteen of them are four copies of eight’s diamond, one in each quarter. The other twelve are every point of the colour on the middle row and the middle column except the centre. Those twelve cuts separate the four quarters along both midlines, everywhere but at the centre join, which is kept and is the only place the quarters meet. The thirty-two-by-thirty-two doubled tree is the same shape again: a hundred and twelve cuts in the quarters, four copies of sixteen’s, and twenty-eight on the middle cross.

The loop count agrees piece by piece. A perfect tree on a grid of side $2k$ has four quarters of side $k$, each with its own loops, and a cross whose loops are the ones along the midlines. On sixteen that is four times twelve loops in the quarters and thirty-six along the cross, broken by four times four cuts and twelve cuts; on thirty-two, four times eighty-four and eighty-four, broken by four times twenty-eight and twenty-eight. The cross costs exactly one cut for every three of its loops, like everything else, and it is what makes four trees into one.

That is the cut-side reading of why doubling reaches only the powers of two. A cross can separate four quarters only if each quarter holds a perfect tree of its own, and a quarter of a ten-by-ten grid is five by five, a quarter of fourteen seven by seven, both odd and so without a tree. Twenty’s quarters are ten by ten, which has none. The case analysis says more than this — that no arrangement other than a doubled one exists on ten or fourteen — and the doubling says why the ones that exist look the way they do.

What the cut reading assumes #

It is the earlier essays’ model, restated. Joins are at lattice points and each keeps the four cranes that meet there; a perfect tree has exactly $(n^2 - 1)/3$ joins, each merging four pieces; its joins lie on one colour, as the earlier essay proved. The cut reading adds nothing to those rules; it only counts the same objects from the other side.

The equivalence rests on two counts that are exact. The loops are the squares of four links, and there are three times as many of them as cuts; removing a point with four links and no removed neighbour removes three of them. Everything else follows from the fact that a graph with no loop and one piece is a tree.

The search is exhaustive and its case count depends on its order. Seven is the number of branches this search takes, choosing the untouched loop with fewest possible cuts and breaking ties by position. A different order would reach the same verdict in a different number of cases, possibly fewer. The claim is that seven suffice and are drawn, not that seven is the least a proof could use.

And nothing here is about the 1797 plates. Whether the book drew any arrangement that is a perfect tree is a question about the plates, and a record is not a proof runs both ways: a proof about which arrangements exist is not a record of which were folded.

The loops were always a third #

The unexpected fact is the three. Every even grid’s colour has exactly three times as many loops as a perfect tree has cuts, and that is not a property of the powers of two or of the book; it is the floor $(n^2 - 1)/3$ and Euler’s count saying the same thing. It is the same three that made a perfect tree’s joins merge four pieces each — one piece in, three pieces joined — and it is why being in one piece is all a set of cuts has to prove.

The loops play the part here that faces play in a crease pattern. A contradiction is even reads a crease pattern’s consistency off its faces, a loop of panels at a time, and a single face that cannot be coloured is the whole of a failure. The perfect tree fails the same way on ten by ten: in five of the seven cases one loop is left with no cut, and a single loop is the whole of the failure. In the other two the failure is not at any loop but between regions, which is the global half of the same story — the border is where the cranes come apart found cuttings that failed at the rim and nowhere else, and these two cases are the opposite kind, failing nowhere in particular and everywhere at once.

It also changes the character of the question. The prediction held at eight and broke at ten counted fewest joins over every arrangement; the colour essay counted trees over one colour’s points; this counts cuts over one colour’s loops, and each count is smaller than the last because it builds in more of what is already known. Local is not global holds here too: every stranded loop in the seven cases is stranded by cuts that each looked fine where they were made.

Still open: a reason that is not a list #

Seven cases settle ten, and they do not generalise. Fourteen takes 761 and sixteen 28,775, and nothing in the list for ten says what makes a power of two special. The shape the cuts take when they succeed — a cross between four quarters, repeated — suggests the argument: that any perfect tree on a grid of side $2k$ must contain the whole middle cross of cuts, which would make its quarters perfect trees of side $k$ and reduce every even grid to its odd part. The case analyses are consistent with that, and proving the cross is forced would prove that perfect trees exist exactly on the powers of two.

Twenty, and the open sizes past it, want a faster search. Twenty-two, twenty-six and twenty-eight were beyond the join search, and twenty is beyond this one. A search that first placed the middle cross and then asked whether each quarter could be completed would settle them quickly if the cross is forced — and would find, if it is not, the first perfect tree of a new kind.

Sideways from here, even is not enough found the same shape of result for crease patterns: a two-colouring necessary and not sufficient, with the extra condition global. Here the extra condition is one piece, and a seven-case list is what it looks like on a grid small enough to list.

The habit worth carrying is about describing a solution by its complement. When a solution keeps most of what it could, count what it leaves out. A perfect tree keeps thirty-three of forty-one points on ten by ten and cuts eight; the eight are where the structure is, and the loops they must break are three times as many as they are, on every grid.