Characterize those non-empty graphs with the property that every two distinct maximal independent set of vertices are disjoint > > An independent set of vertices in a graph $G$ is **maximal independent** if $S$ is not a proper subset of any other independent set of vertices in $G$. Characterize those non-empty graphs with the property that every two distinct maximal independent set of vertices are disjoint I'm not sure if I understand this correctly, but independent set is a set of vertices such that non of them are adjacent to each other, and we are looking at the maximal indepeendt set of vertices. I'm not sure about how they want me "characterize". But I guess for a bipartite, you can find 2 distinct maximal independent set that are disjoint. Please correct me if I'm wrong, and help me understand this better.

HINT: Suppose that maximal independent sets of vertices of $G=\langle V,E\rangle$ are pairwise disjoint. Define a relation $\sim$ on $V$ by $u\sim v$ iff $\\{u,v\\}$ is independent.

* Show that $\sim$ is an equivalence relation on $V$.
* Show that for all $u,v\in V$, $uv$ is an edge of $G$ iff $u\
ot\sim v$.
* Show that if $\\{V_1,\ldots,V_n\\}$ is the set of $\sim$-equivalence classes, then $\\{V_1,\ldots,V_n\\}$ is a partition of $V$ into maximal independent sets, and $G$ is the complete $n$-partite graph with parts $V_1,\ldots,V_n$.