Suppose we have a **k-hypercube** $(Q\_k)$ where $k$ is an odd integer.


Define $F(A)$ for $A \subseteq V$ as the set of all vertices such that has odd number of edges to the set $A$.


Is it true that $F(F(A)) = A$?



Is $F(F(A)) = A$ for every k-hypercube where k is odd?
* **Lemma 1:** $\space F(U \Delta V) = F(U) \Delta F(V)$.


**Prove:** By using $S\_1 = S\_2 \iff S\_1 \subseteq S\_2 \land S\_2 \subseteq S\_1$ we can prove this equality.


	1. Suppose $c \in F(U \Delta V)$, we know $c$ has odd number of neighbors in $U \Delta V$ by the definition of $F$. By parity
	and the definition of symmetric difference we know $c$ has odd
	number of neighbors to exactly one of the $U \setminus V$ and $V
	 \setminus U$; It means $c$ has odd number of neighbors in
	exactly one of the $U$ and $V$ which implies that $c \in F(U) 
	 \Delta F(V)$. This proves $F(U \Delta V) \subseteq F(U) \Delta
	 F(V)$.
	2. Suppose $w \in F(U) \Delta F(V)$, we know $w$ has odd number of neighbors in exactly one of the $U$ and $V$ by the definition of $F$
	and symmetric difference; It means $w$ has odd number of neighbors
	in exactly one of the $U \setminus V$ and $V \setminus U$ which
	implies that $w \in F(U \Delta V)$. This proves $F(U) \Delta F(V)
	 \subseteq F(U \Delta V)$.By combining these two together we will have $F(U \Delta V) = F(U)
 \Delta F(V)$.
* **Lemma 2:** $F(F(\{x\})) = \{x\}$.  

**Prove**: It's easy to prove by using the definition of $F$ and using the fact that $k$ is odd which tell us that $deg(x)$ is odd.


Suppose $A = \{ a\_i \} \_{i=1}^n$.
By using lemmas we proved and also applying easy induction on **Lemma 1** to get the general form of that (for more than two sets) we will have:
$$
F(F(A)) = F(F(\{ a\_i \} \_{i=1}^n)) = F(F(\Delta\_{i=1}^n a\_i)) = F(\Delta\_{i=1}^n F(a\_i))
= \Delta\_{i=1}^n F(F(a\_i)) = \Delta\_{i=1}^n a\_i = \{ a\_i \} \_{i=1}^n = A
$$
And done we proved $F(F(A)) = A$.
$$\tag\*{$\blacksquare$}$$


