Let $G$ be a regular $n$-vertex graph which is edge transitive. How large can the degrees of $G$ be if it is not a complete $r$-partite graph?


The best I can do is about $n/2$ by considering two disjoint cliques of the same size. A relatively easy argument shows that any $n$-vertex edge transitive graph with degree $n-o(\sqrt{n})$ must be complete $r$-partite, so one can not hope to do better than this. I'd be interested to see improvements to either of these two bounds, and in particular in knowing whether there can exist such graphs with degrees $n-o(n)$.



Super dense edge-transitive graphs
Take $G=\overline{K\_m\square K\_m}$, the complement of the Cartesian product of two copies of the complete graph on $m$ vertices. It has $m^2$ vertices, valency $(m-1)^2$ and is edge-transitive. (In fact, we have $\mathrm{Aut}(G)=S\_m\wr S\_2= (S\_m\times S\_m)\rtimes S\_2$.)


