Given a connected graph $G$ with vertex set $V(G)$, a set $S\subseteq V(G)$ is called a dude set if every vertex of $V(G)\setminus S$ is adjacent to at least one vertex of $S$. Let $\mathcal{D}$ denote the collection of all dude sets of G. As usual, the $0-1$ vector $x(S)\in \mathbb{Z}^{V(G)}$ with $x_u(S)=1$ if $u\in S$ and $x_u(S)=0$ if $u\neq S$ is called the characteristic vector of $S$. The convex hull of the set $\{x(S):S\in D\}$, denoted by $P_{\mathcal{D}}$, is called the dude-set polytope of $G$. If $u\in V(G)$ is a vertex of $G$, the neighborhood of $u$ in $G$, denoted by $N(u)$, is the set consisting of $u$ together with the vertices that are adjacent to $u$ in $G$.
(a) Prove that $P_{\mathcal{D}}$ has dimension $|V(G)|$
(b) Suppose that $u$ is any vertex of $G$. Prove that the inequality $x_u\leq 1$ describe a facet of $P_{\mathcal{D}}$.
(c) Suppose that $u$ is any vertex of $G$. Suppose that $|N(u)|\geq 3$ for every $v\in N(u)$. Prove that the inequality $x_u\geq 0$ describes a facet of $P_{\mathcal{D}}$.
(d) Assume now that $G=G_n$, a cycle on $n$ vertices (with no other edges other than $n$ edges of the cycle itself). Prove that the cycle inequality \begin{equation} \sum_{v\in V(C_n)}x_v\geq \lceil\frac{n}{3}\rceil \end{equation} is valid for $P_{\mathcal{D}}$, and moreover, when $n>3$, that it describes a facet of $P_{\mathcal{D}}$ if and only if $n$ is not a multiple of $3$.($\lceil z \rceil$ denotes the least integer greater than or equal to $z$)
Any ideas or thoughts will be greatly appreciated!
