Properties of Cuts


Before even stating the problem, I want to prove two facts about cuts of snakes that will be central to my later proofs.

  • Possible proper vertical or horizontal cuts of a snake can intersect zero or two edges of one matching, but it cannot intersect exactly one edge:

    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:




  • When do two matchings of the same snake S have a common proper vertical or horizontal cut?
    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.

  •