Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A graph $G$ is said to be edge transitive provided that, for any two edges $e$ and $f$ in $G$, there is an automorphism of $G$ sending $e$ to $f$.

Call a graph good if it satisfies the following conditions:

  1. $G$ is connected.
  2. $G$ is edge transitive.
  3. For any edge $uv$, the graph $G - \{u,v\}$ is edge transitive.

(By $G - \{u, v\}$, I mean the graph $G$ with vertices $u$ and $v$ removed, as well as all edges incident to either $u$ or $v$.)

Any complete or complete bipartite graph is good, since the removal of any two vertices results in a smaller complete or complete bipartite graph, respectively, which are edge transitive.

The cycle on five vertices is also good, but larger cycles are not. I consider this to be sporadic instance and is not particularly useful for my purposes (though I would still be interested to hear about others).

I think a statement like "A graph is good if and only if it is complete, complete bipartite, or one of these finitely-many graphs" is true, hopefully with a very small "finitely-many". I would be interested in thoughts toward a proof or other examples of good graphs.

share|cite|improve this question
Perfect matchings are good, too, as is any union of disjoint 3-cycles. And any forest of identical stars. – Henning Makholm Jan 2 '12 at 3:48
@HenningMakholm I had in mind that $G$ should be connected, but failed to mention it. I will edit accordingly. – Austin Mohr Jan 2 '12 at 3:50
up vote 5 down vote accepted

Lemma. An edge-transitive graph has at most two vertex degrees. If there are two different degrees, then the graph is bipartite. (Proof omitted).

Theorem. The only good graphs are (a) complete graphs, (b) complete bipartite graphs, (c) the 5-cycle.

Proof. Assume first that $G$ is acyclic, i.e. it is a tree. Then, in order for it to be edge-transitive, each edge must have a leaf node at one end. Thus, the graph is a star, which is a special case of complete bipartite.

Otherwise, consider a shortest cycle in $G$.

  • If it has length 3, say $ABCA$. Since $G$ is edge-transitive and contains an odd cycle, it must be regular. After deleting, say, $AB$, the degree of $C$ has decreased by $2$.

    Now, suppose $G$ contains a node $P$ that is neighbor to neither $A$ nor $B$. Then the reduced graph must be bipartite. But then every $3$-cycle in the original graph must have included either $A$ or $B$ (or both). This contradicts the fact that by edge-transitivity $P$ must have been part of some 3-cycle.

    On the other hand, suppose $G$ has a node $Q$ that was neighbor to $A$ but not to $B$. Then, because again the reduced graph is bipartite, all of $Q$'s neighbors must be of the kind that was neighbor to both $A$ and $B$. So every neighbor of $Q$ is also a neighbor of $A$. Since $G$ is regular, this means that $Q$ and $A$ have the same neighbors, contradicting the assumption that $QB$ is not an edge.

    Thus every vertex was originally connected to both $A$ and $B$. But then, by edge-transitivity, each endpoint of any edge is connected to every other vertex, so $G$ is complete.

  • If it has length 4, say $ABCDA$, then after deleting $AB$, both of $C$ and $D$ vertices have one less degree. In order to preserve edge transitivity then, every remaining vertex must have its degree decrease by $1$. Thus every vertex is neighbor of exactly one of $A$ or $B$ -- in other words $G$ is partitioned into neighbors of $A$ and neighbors of $B$, and there cannot be any edge inside either of the partitions because that would constitute a 3-cycle. Thus $G$ is bipartite. Because it is edge transitive, every edge is as well connected as $AB$, so it must be complete bipartite.

  • If it has length 5, say, $ABCDEA$, then deleting $AB$ will leave the remaining edges $CD$ and $DE$ with a node of less degree at one end, namely $C$ and $D$. If the result is still edge transitive, then every vertex connected to $D$ must also be initially connected to one of $A$ and $B$ (because its degree must have decreased). But if there is such a node except for $C$ and $E$, there would have been a 4-cycle to begin with, contradicting the minimality of 5. Thus the graph was originally $2$-regular, that is, it was the 5-cycle.

  • If it has length 6 or more, then deleting an edge and its endpoints will leave the graph with too many different node degrees ... except if the graph was initially regular, but then after deletion there will be edges that touch a node with reduced degree and edges that don't, so the result isn't edge transitive. Therefore length $\ge 6$ is impossible.

Corollary. Removing two neighbor nodes from a good graph produces either a good graph or a graph with no edges at all.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.