(Solved): Problem 3: Cutset Expansion of 3n-cube Consider a graph whose vertices are all 3n words over {a,b, ...

Problem 3: Cutset Expansion of $$3^n$$-cube Consider a graph whose vertices are all $$3^n$$ words over $$\{a,b,c{\}}^n$$. Moreover, there is an edge between two vertices if and only if the two corresponding vectors differ in exactly one position. Prove that the above graph has coutset expansion at least 1 (if you can't prove it for 1 , any constant $$c>0$$ is also fine.)