Can the number of minimal vertex covers of a graph be super-polynomial (like exponential)? I suspect it can, but can't think of any examples.


**Vertex cover** $C$ of a graph $G$ is a subset of its vertices that any edge has an incident vertex in that set. That is:
$$
C\subseteq V(G)
\hspace{1cm}
\text{s.t.}
\hspace{1cm}
\forall\_{xy\in E(G)} x\in C \vee y\in C
$$


**Minimal vertex cover** $C$ of a graph $G$ is a vertex cover of $G$ such that the set $C'$obtained by removal of any vertex from $C$ is not a vertex cover of $G$. That is:
$$
C \text{ is a vertex cover}
\hspace{1cm}
\wedge
\hspace{1cm}
\forall\_{v\in C}C':= C-v \text{ is not a vertex cover}
$$



Bound on the number of minimal vertex covers of a graph
The union of $k$ triangles has $3^k$ minimum vertex covers. You can easily find connected examples.


