We have a graph $G$ with binary values on it's vertices. If we flip the value of an vertex $v$ $ \forall v \in V(G)$ (that is, from $o_v$ in $\neg o_v$, where $o$ is the value of the vertex $v$). And the values of it's neighbors will flip as well, so the value of $w$, $\forall w \in N_G(v)$ will flip from $o_w$ in $\neg o_w$.
The interesting property to this type of graph is that if all the vertices have the same value $o$, then there exists a set $S$ that if the flip the vertices in $S$, one at a time (no matter the order), then all the vertices in the graph will have the same value $\neg o$.
By $m(v, X)$ we denote the number of edges from the vertex $v \in V(G)$ to > the subset $X \subseteq V(G)$
List the proprietes of $m(v, S)$ and $S$ ($\forall v \in V(G)$).
My try:
There are 2 cases for this problem. If the graph $G$ is a connected graph then we need to flip only one node to get from $o$ to $\neg o$. And $|S| = 1$ and $S$ can be made from any node in the graph. Also, because of this $m(v, S) \in \{0, 1\}$.
If the graph is not connected, it will be partitioned in $k$ connected partitions. This means that $|S| = k$, $S$ will have only one node from each partition.
How will you approach this problem?
