Proof or disproof of the existence of a way to flip all bits on a (undirected) graph

Question

Suppose there is an undirected graph $G=(V,E)$. Each node $v\in V$ is allowed to be labelled either "$0$" or "$1$". Define an "operation" $f_v$ for each $v\in V$ which toggles the label for $v$ and all $v$'s neighbours (i.e. all the other $v'\in V$ such that $v'$ is connected to $v$ via some edge $e'\in E$) to the opposite label. Initially, each node is labelled "$0$".

Question: Prove or disprove that we can toggle all labels to "$1$" only by performing the operations $\{f_v\mid v\in V\}$.

Sorry, I have no idea where to start since I'm not familiar with graphs at all... I don't even know whether the statement is true or false. Could somebody kindly tell me how to prove/disprove it or at least where to look? Thanks.

---

EDIT As pointed out in comments, not a counter-example: first toggle the top and bottom nodes in the first column, and then the single node in the third column.

Failed attempt: Not sure if the following furnishes a counter-example but here it goes:

---

Background This question came from a friend of mine who was inspired when he was having a Chinese family dinner. In such family dinners, a very pronounced type of activities is "propose toasts" i.e. one will toast to his families for good fortune etc and then this person and all the people he toasts to will drink up their wine ("bottom up") and then refill for the next round of toasting. So now let's imagine a huge Chinese dinner with lots of people and some know each other but others don't. And let's suppose additionally:

1). If somebody is gonna propose a toast, they toast simultaneously to everybody they know but not to those they don't know. (By the way, "knowing" is a reciprocal relation here, A knows B if and only if B knows A.)

2). There are two types of wine: beers and Chinese spirits. And when one drinks up their current glass, they will refill it with the other (alternating) type of wine.

Initially everybody has their glass filled with Chinese spirits. Is it possible that everybody ends up with beers in their glass?

Answer 1

The statement is true. The Garden-of-Eden paper of Sutner studies the problem using cellular automata.

Here is another shot using linear algebra. First, notice that if you perform the operations $f_{v_1}, \dotsc, f_{v_k}$, the order on which these operations are performed does not matter, they all give the same output. Next, performing the same operation $f_v$ twice cancels itself. Thus it is enough to find $S \subseteq V(G)$ and perform $\{ f_v : v \in S \}$.

We might phrase this problem as a system of linear equations in $\mathbf{F}_2$, the field with two elements. Let $A$ be the adjacency matrix of the graph $G$ and let $I$ be the identity matrix whose rows and columns are indexed by $V(G)$. If $S \subseteq V(G)$, let $\chi_S$ be the (column) $\{0,1\}$-vector indexed by $V(G)$ with an $1$ in the coordinate $v$ if and only if $v \in S$. Then the problem is equivalent to solving the system $(A + I)\chi_S = 1$ over $\mathbf{F}_2$, where $1$ is the all-ones vector. To solve the problem then it is enough to see that $1$ is in the range of the matrix $(A+I)$. That is exactly the approach taken here, and the proof is very simple.

Answer 2

The statement do not seem to true in general, well you may add another condition of connected graph without any cycle to check whether the statement is true or not

I think I have found a counter example for the general case ,

Consider a graph with a three cycle , two of whose vertex (name them as A) has degree two and the the third one may have degree >=2. Say we have initially opposite number assigned to them (A vertices), now it seems from here we cannot make the A vertices have same number because toggling any vertex preserves the opposite number assigned to A vertices.