A graph is without solvable orbits if its group of automorphisms acts on each of its orbits through a non-solvable quotient. We prove that there is a connected graph without solvable orbits of cyclomatic number c if and only if c is equal to 6, 8, 10, 11, 15, 16, 19, 20, 21, 22, or is at least 24, and briefly discuss the geometric consequences.
, , , , , , , ,
Institut des Hautes Etudes Scientifiques preprint
Spinoza prijs Lex Schrijver
Networks and Optimization

Karolyi, G, & Pal, A. (2007). The cyclomatic number of connected graphs without solvable orbits. Institut des Hautes Etudes Scientifiques preprint. IHES.