$G$ is a graph whose vertices are all $3$ element subsets of $\lbrace{1,2,3,4,5,6}\rbrace$. Sets A and B are considered adjacent vertices of G if they have exactly one number in common and that number is the cost of the edge AB. Find a cheapest spanning tree of G.
My solution: Graph $G$ is to be taken and the $3$ element subsets are chosen from $\binom{6}{3} = 20$, so there are $20$ subsets taken from the array. {$1,2,3$}, {$1,3,4$}, {$1,4,5$}, {$1,5,6$},{$2,3,4$},{$2,4,5$},{$2,5,6$} and so on..
I assume that we have to take subsets with a common element and mark it as a vertex, once chosen I would apply Kruskal's algorithm to find the cheapest cost based on the Edge's weight, and the weight determined by the common element between two vertices.
There are $10$ edges between the vertices.
I'm not sure how to put it in a formal proof? could anyone show me how to do so?
The vertex $ \{ 1,2,3 \}$ is joined to the $9$ verticies of the form $ \{ a, B,C \}$ where $ a \in \{ 1,2,3 \}$ and $B , C \in \{4,5,6 \} $. The next layer consists $9$ verticies is of the form $ \{a,b,C \}$ where $ a,b \in \{ 1,2,3 \}$ and $ C \in \{4,5,6 \} $. There is then a final layer consisting of the $1$ vertex $ \{ 4,5,6 \}$.
There $10$ verticies are of the form $ \{ 1, x,y \}$ where $x,y>1$; There $6$ verticies are of the form $ \{ 2, x,y \}$ where $x,y>2$; There $3$ verticies are of the form $ \{ 3, x,y \}$ where $x,y>3$; There is $1$ vertex are of the form $ \{ 4, x,y \}$ where $x,y>4$; and this is the full list of $20$ verticies.
The cheapest spanning tree will be obtained by joining each set by its smallest element. Such a tree can formed as follows ...
Join $ \{1,2,3 \}$ to its $9$ nearest neighbours. Join each of the $3$ sets $ \{ 1, A,B \} $ to the $2$ sets of the form $ \{1,a,C \}$ where $A,B,C \in \{4,5,6 \}$ and $a=2$ or $3$. Join each of the $3$ sets $ \{ 2, A,B \} $ to the $2$ se sets of the form $ \{2,3,C \}$ where $A,B,C \in \{4,5,6 \}$. Finally join the vertex $ \{4,5,6 \}$ to $ \{ 1,2,4 \}$.