Bijection between leaf-free subgraphs of the Möbius ladder and the ladder graph.

59 Views Asked by At

There are the same number of leaf-free1 subgraphs on the ladder graph $L_{n+2}$ and on the Möbius ladder2 $M_n$, which is given by OEIS sequence A020876. Furthermore, these graphs have a very similar structure3.

I'm looking for a bijection that respects that structure. In particular, I feel like the two subgraphs with no edges should map to each other, and the two subgraphs with all of the edges should map to each other.


Example

For example, when $n = 2$ there are $15$ leaf-free subgraphs of $M_2$ enter image description here and $15$ leaf-free subgraphs of $L_{4}$: Fifteen 2 by 4 leaf free subgraphs.


1 A leaf-free subgraph is a subgraph with no vertex has degree exactly one.

2The Wikipedia article uses a different convention from the OEIS sequence. I use the OEIS convention: $M_n$ has $2n$ vertices.

3You can think of the relationship between $M_{n}$ and $L_{n+2}$ as being analogous to the relationship between a rectangle and the Möbius strip made from that rectangle, by identifying the ends with a twist.