Planar graph with an exponential amount of matches?

Question

I need a planar graph with an exponential amount of matches.

Was wondering is there a good example of this?

I'm finding it hard to believe that its possible to have such a graph.

I was thinking and all I could come up was this

Or maybe something that looks like a chess board. In an $n \times n$ chessboard is there an exponential amount of ways with respect to n to cover the chessboard with dominoes?

Answer 1

An exponential number of matchings occurs when we take disjoint copies of $K_2$. Specifically it will have $2^{\#\text{edges}}$ matchings. The graph is trivially planar.

Variations of this graph still give exponentially many matchings, e.g.

for a connected graph, or

for a connected graph without bridges.

---

In the case of perfect matchings, an exponential number can be achieved by taking disjoint $4$-cycles. Specifically we have $2^{\#4\text{-cycles}}$ perfect matchings.

Answer 2

As you said consider a $2n \times 2n$ cheseboard (2n vertices). Split it into $n^2$ smaller boards, each of size $2 \times 2$.

The 4 vertices in a $2\times 2$ smaller board form the cycle $C_4$, and there are 2 possible matchings for this mini-board.

Thus, you have $4n^2$ vertices, and you split them in $n^2$ groups, with 2 perfect matchings per group. We found thus $2^{n^2}$ distinct perfect matchings, and of course there are much more...

P.S. I think this solution is somehow similar to Douglas idea of taking distinct copies of $C_4$.