Proving the graph $V=\{S\subset\{1,2\ldots9\}\mid3\leq\left|S\right|\leq4\},\,\,\,E=\{(u,v)\mid u\subset v\}$ is connected

Question

Let $G=\left\langle V,E\right\rangle$ be an undirected graph with $V=\left\{ S\subset\left\{ 1,2,\ldots,9\right\} \mid\left|S\right|\in\left\{ 3,4\right\} \right\}$ and $E\left\{ \left(u,v\right)\mid u\subset v \lor v\subset u\right\}$ . I'd like to prove this graph has an Eulerian cycle, so in addition to showing the degree of all vertices is even (Easy enough) I also want to show it is connected, but every attempt so far ended up very messy, with division into cases for existence of a path between any two vertices. Is there a more elegant way?

Answer 1

It seems like the easiest way to do this would be via induction. Let $G_n$ be the graph on the $3$- and $4$-element subsets of $\{1,\ldots, n\}$, with the same rule for edges. It's easy to see that $G_4$ is connected (why?). Given that $G_{n-1}$ is connected, in order to prove that $G_n$ is connected, it would suffice to take an arbitrary vertex in $v \in V(G_n) \setminus V(G_{n-1})$ and show that it has a path to some vertex in $G_{n-1}$. Connectedness of $G_{n-1}$ would then suffice to get from $v$ to any vertex you want, including the other vertices of $V(G_n) \setminus V(G_{n-1})$, although it's probably worth fleshing that argument out in more detail for yourself.

Answer 2

Hint: think of a path from $S_1 \in V$ to $S_2 \in V$ as a sequence of operations $S \mapsto S'$ where $S'$ is obtained from $S$ either by adding a new element if $|S| = 3$ or deleting an element if $|S| = 4$. Now design a strategy that will transform any given $S_1$ into any desired $S_2$