Let $G(V,E)$ be a Graph such that: $$V=\left \{ X\in P(\left \{ 1,2,3,4,5,6,7,8 \right \}) \ |\ \left | X \right |=4\right \}$$ $$E=\left \{ \left \{ X,Y \right \}\in V\times V \ |\ \left | X\Delta Y \right |=4\right \}$$
Hey I don't now how this graph looks like since I think that the vertices are not numbers and I'm totally confused about this. Can someone tell me how this graph looks like and does it have Hamiltonian Cycle, Eulerian Cycle or Planar Graph?
- I think that $|V|= $$8 \choose 4 $ I don't know if that helps but I know if the degree of all vertices in $G$ are even then $G$ contains an Eulerian Cycle, and from $Dirac$ princple that if $\forall v\in V \ deg(v)\geq \frac n 2$ then $G$ contains Hamiltonian Cycle.
Can someone help me please? simplify the graph and explain how it looks like and if possible try to proof the given or give a counter example to this problem!
Thanks a lot!
Each vertex of the graph is a subset of four elements of $\{1,2,\ldots,8\}$
As you said, $|V|={8\choose 4}=70$
WLOG we can take the vertex $\{1,2,3,4\}$ and we notice that the adjacent vertices need to have two elements from $\{1,2,3,4\}$ and the other two from $\{5,6,7,8\}$ (in order for the symmetric difference to have $4$ elements).
So, by symmetry, the degree of each vertex is ${4\choose 2}\cdot{4\choose 2}=36\ge\frac{70}{2}$ and even.
So the graph has both Eulerian and Hamiltonian cycles.
The number of edges of the graph is:
$|E|=\frac{1}{2}\sum_{i=1}^{70}36=1260$
A necessary condition for a connected graph to be planar is that $|E|\le 3|V|-6$ (Euler), which is not the case here.
NOTE: Of course, in order to apply the theorems above you need to prove first that the graph is connected. This can be easily done by considering how many common elements the vertices have. For example, if the vertices have one common element, WLOG say $\{1,2,3,4\}$ and $\{1,5,6,7\}$, they can be connected as $\{1,2,3,4\}-\{1,2,7,8\}-\{1,5,6,7\}$. The cases with $0$, $2$, $3$ and $4$ common elements are similarly trivial.
An alternative way to prove that the graph is not planar is to show (for example) that the subgraph formed by $\{1,2,3,4\}$, $\{1,2,3,5\}$, $\{1,2,3,6\}$, $\{1,2,7,8\}$, $\{1,3,7,8\}$, and $\{2,3,7,8\}$ is isomorphic to $K_{3,3}$ and use Kuratowski's theorem.