Attribute of the graph of transpositions

55 Views Asked by At

Let $\Gamma$ be a graph, the vertices of $\Gamma$ are the transpositions of $S_n$. Two vertices are connected with an edge iff the two transpositions have a common moved point.

Prove that if $n \geq 5$ then every $n-1$ point complete subgraph of $\Gamma$ is of the form $G_a:= \{(a,x) | x \in \{1,2,...,n \} \setminus \{a\} \}$, in other words the vertices of this subgraph are all transpositions with exactly $1$ common moved point $a$.

As far as I know, a cycle with only two elements is called a transposition. For example, $(3,4)$ and $(3,5)$ are connected in the graph, since they all move the same point, which is $3$.

The task says, that we can only get a complete graph in such way: every edges must have the form $(a,x)$, where $a$ is a fixed element from the $\{1,...,n\}$ set, and $x$ can be anything except $a$.

Let us take an $n-1$ point complete subgraph from $\Gamma$. For this to be complete, every $2$ nodes must be connected to each other, meaning, that every two transpositions must have a common moved point. This means, that all of this $n-1$ transpositions must have a common moved point, let's say $a$. Then every transposition looks like $(a,x)$, which was the task to prove.

Is my approach correct?

Any help appreciated.