Before even stating
the problem, I want to prove two facts about cuts of snakes that will be central
to my later proofs.
This can be easily seen from the area argument. If a possible proper (say)
horizontal cut intersected a matching in exactly one edge, then we would
be left with two sections of a snake that have an odd number of vertices.
Therefore we cannot find matchings for these two sections of the snake.
Ex:
Maybe a better question to ask is:
What are the matchings of snake S that do not have a common proper
vertical or horizontal cut?
The simplest way to look at this problem is to consider the "proper borderline"
of a snake.
Here's an example of how to construct the "proper borderline" of a snake:
If two matchings, A and B, of a snake S, do not share a common proper vertical
or horizontal cut, then the edges on the proper borderline must alternate
between the matchings A and B:
As we see above, one of the matchings will have all the vertical z-edges
and two y-edges for each column and the other matching will have all the horizontal
z-edges and two x-edges for each row.
Those are the only two matchings of a snake that do not share a common
cut. Their snake matching polynomials are z^(height-2)*y^width and z^(width-2)*x^height.