Let $G$ be a finite simple graph on a vertex set $\{x_1,...,x_n\}.$ Let us call a vertex cover of $G$ to be minimal if none of its proper subset is a vertex cover. Let $C_1,...,C_h$ be the collection of all minimal vertex covers of $G$.
Let $\Delta$ be the abstract simplicial complex on the vertex set $V:=\{i: 1\le i\le n; \{x_i\} \text{ is not a minimal vertex cover} \}$ and the faces of $\Delta$ are the proper subsets of $C_i$ s.
My question is:
Can we find the dimension of $\Delta$ in terms of some invariant of $G$?
I feel that $\dim \Delta =\min_{i} |C_i| -1$, but I'm not sure.
Please help.
The faces of $\Delta$ are the proper subsets of the $C_i$. The dimension of $\Delta$ is the dimension of a face with maximal possible number of vertices. Such a face is obtained by choosing $C_j$ that has maximal cardinality among the $C_i$ and then removing one element $x\in C_j$ to obtain $F=C_j\setminus\{x\}$.
Hence $$ \dim\Delta = \dim F = |F|-1 = |C_j|-2 = \max_{i=1,\dots,h} |C_i| - 2. $$