Is there for every $n\in\mathbb{N}$ a connected, simple, undirected graph $G_n=(V_n,E_n)$ such that $G_n$ has exactly $n$ perfect matchings?
$\begingroup$
$\endgroup$
asked Sep 23, 2018 at 12:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
11
I will let the picture speak for itself.
-
$\begingroup$ @wojowu Think you can make for $n^2$ at every $n>5$? $\endgroup$– TurboCommented Sep 23, 2018 at 13:40
-
$\begingroup$ @Freeman. For $n^2$ what? If you want a graph with $n^2$ matchings, replace $n,n-1$ in my construction with $n^2,n^2-1$. $\endgroup$– WojowuCommented Sep 23, 2018 at 13:42
-
$\begingroup$ @Wojowu No graph has to have $2n$ vertices. $\endgroup$– TurboCommented Sep 23, 2018 at 13:50
-
$\begingroup$ @Freeman. prntscr.com/kxpgs3 $2n+2$ vertices $\endgroup$– WojowuCommented Sep 23, 2018 at 13:54
-
$\begingroup$ @Wojowu I think that graph has $n$ perfect matchings; the top and bottom choices are not independent (and in fact must be the same). $\endgroup$ Commented Sep 23, 2018 at 13:59