We define set partition graph as follows: Consider a set $\{1,2,..,n\}$ where $n\geq2$, the vertices in our graph are all the set of partition of $\{1,2,..,n\}$. Now, two vertices $V$ and $V'$ connect with an edge if every block in $V$ is a union of blocks in $V'$ or vice versa. For instance, $\{\{1,2\},\{3\}\}$ has an edge connect to $\{\{1,2,3\}\}$ but not $\{\{1,3\},\{2\}\}$. An example for $n=3$ shown below.
The question asks to prove the graphs is connected for $n \geq 4$. I'm not sure in what way we can prove this particular set partition graph is connected. I'm essentially stuck here for a while.
Additionally, if we remove the vertices with partition $1$ parts and $n$ parts, does the graph still connect? and why?
For this part, my interpretation is we are removing the top node and bottom node, if we consider they are the two root of the tree, then it's clearly not connected if we remove them. But I think I'm having a weak argument here, wonder is there a formal proof for it.
Any hint or suggestion that help me go further would be appreciate!!
First we show that for all $n$ the partition graph $G_n$ of the set $[n] =\{1,...,n\}$ is connected. This follows from the fact, that every vertex $v$ is connected to the dedicated vertex $\{[n]\}$ by iteratively taking the union of the subsets in the partition corresponding to $v$. If you are unhappy with this argument I suggest an induction on the number of subsets in the partition.
Obviously we could also have chosen to show that every vertex $v$ is connected to the dedicated vertex corresponding to the partition by singleton sets.
Now if you remove those two dedicated vertices from $G_n$, is the resulting graph $H_n$ still connected? I don’t know if it matters to you, but for $H_3$ it is not true. For $H_n$ with $n\geq 4$ it is however. Note that you can iteratively find a path between any two vertices by chopping and gluing partitions in such a way that you never have exactly 1 or exactly $n$ partitions. To make this argument more formal I would suggest using that all partitions containing a fixed subset $\{i,j\}$ (with $i\neq j$) are connected and that (from $n\geq 4$ onwards) you can connect any two of the partitions of the form $\{i,j\}$+singletons.