Polyhedral triangulations that are z-knotted (a.k.a., unicursal or single left-right cycle) occur more frequently than intuition might expect. Plantri can generate all polyhedral triangulations up to, say, a couple dozen vertices, and we can test them for unicursality using standard software to count spanning trees. Shank's Theorem (1974) says: Given a connected planar graph G having H(G) spanning trees, G is unicursal if and only if H(G) is odd.
For 3-connected planar triangulations the chart above tells the tale up to 16 vertices, both for the general case and with various caps on maximum vertex degree (that often being a practical necessity.) In the 16-vertex case, the z-knotted fraction is 0.334 in the general case, and nearly unchanged until the cap on vertex degree falls to 6, where the knotted fraction falls to 0.221.
Though these sizeable fractions come as a jolt to intuition, one might also reasonably expect that counts of spanning trees would be odd 50% of the time. Well, not quite.
What happens to these fractions as vertex counts go upward of 10,000 or more? It is hard to reach higher vertex counts while examining each and every graph because the numbers of graphs in each vertex cohort are already immense and growing rapidly. Plantri generates graphs in a fixed order, so there is no way we can get a random sample other than by randomly selecting from the entire generated set. Also, knotted-ness shows a tendency to be more common in the graphs that Plantri generates first.
Though Shank's Theorem applies only to connected planar graphs, let's back out and look at a more general class of graphs. Kirchhoff's Matrix Tree Theorem (1847) applies to any sort of graph, connected, disconnected, multigraph or simple. The Matrix Tree Theorem says we can get the count of spanning trees in a graph by calculating the determinant of any minor of a matrix called the Laplacian (which is just the graph's adjacency matrix multiplied by -1, with the diagonal elements filled in with the degree of that respective vertex.) Since we are only interested in the parity of the determinant, all the values in the Laplacian can be mod 2 reduced to 0 or 1, and likewise the calculations of the determinate can be done in mod 2 arithmetic (where, for example, there is no distinction between addition and subtraction!)
The Laplacian of an arbitray graph on n vertices, even after it is reduced to mod 2, not a random integer matrix since the elements on the diagonal have the parity of the sum of the other elements sharing that row or column. For that reason a minor of the Laplacian is not truly random but close.
Taking the dual does not change the cursality of a plane graph; it will be more convenient to study the duals of the 3-connected planar triangulations. Quoting from the OEIS page for A000109, "Every planar triangulation on n >= 4 vertices is 3-connected, and its dual graph is a 3-connected cubic planar graph on 2n-4 vertices." So we will be looking at 7-3 through a Laplacian matrix with 2*7-4 = 10 columns and rows, and ultimately through a minor with 9 columns and rows.
The Laplacian of a 3-regular graph is not random; nor is it after modding by 2; nor after forming the submatrix. The submatrix is what concerns us. Like the Laplacian, the minor has 1's along its diagonal and plus 3 additional 1's in each row (and column), but only 2 additional 1's in the 3 rows (and 3 columns) that got robbed when a row and column were taken away. The 1's on the diagonal just make the problem smaller at a given n, so they probably do not affect the limit. Likewise the effect of trimming off a row and column is unlikely to materially affect the properties of large matrices. The other big thing that separates 3-regular graphs' Laplacian minors from random binary matrices of the same size is sparseness. The Plantri 7-3 minor is already down to (4*9 - 3)/9^2 or 41% non-zero elements, so a sparsity of 59%. For Plantri 16-3 (below), there are 28 rows in the Laplacian and the density of the minor is down to 27*4-3/27^2 = 0.144, so a sparsity of 86%.
