Let $G$ be a vertex-transitive graph, with $A$ a clique and $B$ a coclique. Prove that $|A||B| \leq |G|$.
Some observations:
- Let $a_1, a_2 \in A$ and $b_1, b_2 \in B$. If $f,g \in Aut(G)$ such that $f(a_1) = b_1$ and $f(a_2)= b_2$ and $a_1 \not = a_2$, then, $f \not = g$. This is because $a_1 \sim a_2$, but $b_1 \not \sim b_2$, and so, both mapping cannot exist in the same automorphism on $G$.
- It is not true that there is an automorphism $f$ with $f(a_1)=a_2$ and $f(b_1)=b_2$ simultaneously. For instance, consider $G$ to be the union of two copies of $C_6$ with $\{a_1,a_2\}$ and edge, and $b_1, b_2$ on two distinct copies of $C_6$.