# What are the two connected (vertex) transitive graphs with $n=8$, $\deg(G)=3$?

According to McKay in McKay, Brendan; Royle, Gordon F.; The transitive graphs with at most $26$ vertices. Ars Combin. 30 (1990), 161-176., there are exactly 2 isomorphically distinct graphs with 8 vertices and 3 edges per vertex (Table 2: pg 175). I've been able to find one of these on my own:

What is the other graph mentioned here, and more importantly, how do you find this graph without explicit enumeration?

-
Switch the "cross" for a "parallel"; gives you an octogon with 2 rectangles inscribed in it. How did I find it? I just looked at your picture long enough. I am not a pro in graph theory though ; maybe they're isomorphic but I can't see it. Perhaps you could look into that. – Patrick Da Silva Feb 15 '12 at 21:10
"Three vertices per node"? I had thought that nodes and vertices are the same thing---just two different names for it. Could you have meant three edges per vertex (or---what is the same thing---three edges per node)? – Michael Hardy Feb 16 '12 at 1:22
@MichaelHardy, that's correct - editing. – Hooked Feb 16 '12 at 4:17
P.S. : An undirected graph whose vertices all have the same number of edges on them is called a regular graph. The number of edges on a vertex is called its degree. When all vertices have the same degree $k$, we say that the graph is a $k$-regular graph. A $3$-regular graph is also called a cubic graph. Your statement is equivalent to saying that there are two non-isomorphic cubic graphs with eight vertices. Note that you need to add the assumption that the graph is connected ; otherwise the disjoint union of two $K_4$'s (the cubic/complete graph on $4$ vertices) is also an example. – Patrick Da Silva Feb 24 at 23:02

Hm. Like in my comment, I am not sure that my suggestion is the good one, but here's my try :

Take your drawn graph as the first one (which is an amazing picture by the way, good job for putting it there) and define the second graph which is the same but replace $3-2$ by $3-6$ and $6-7$ by $2-7$ (undo the cross, make it parallels). In other words, my new graph would have the edges $$\{0-1, 1-2, \dots, 6-7,7-0, 0-4, 1-5, 3-6, 2-7\}.$$

EDIT: Ok here's a proof that they're not isomorphic : your graph has a $5$-cycle ($3-4-5-6-2-3$). My graph doesn't have such a luxury : the sets $A= \{0,2,3,5\}$ and $B=\{1,4,6,7\}$ have the property that every time you travel from a vertice to another using an edge, you must go either from $A$ to $B$ or from $B$ to $A$. Therefore you cannot go back to $A$ in $5$ steps (i.e. a cycle of the form $a-b-c-d-e-f$ will be such that $a \in A \Longleftrightarrow f \in B$, so that $a \neq f$ and this is not a $5$-cycle).

Since this last argument shows that every cycle in my new graph has even length, we could've also used the fact that your graph has a $7$-cycle $(3-2-6-5-1-0-7-3)$.

Hope that helps,

-
How do you denote an "edge"? I'm curious. I don't remember any standard notation for this! – Patrick Da Silva Feb 15 '12 at 21:17
Or a "cycle"... that would be useful too – Patrick Da Silva Feb 15 '12 at 21:37
Edges are usually denoted $(a, b)$ or sometimes $\{a, b\}$ if the graph is undirected. Knuth uses the same notation you do though---for edges and cycles. – Zach Langley Feb 16 '12 at 3:43

I think there are 5, not 2, isomorphism classes of connected 3-regular graphs on 8 vertices (see https://oeis.org/A002851). But your title has the word "transitive". I don't know what that means, but maybe with that additional qualification there are only two.

EDIT: The vertex-transitive ones are pictured at http://mathworld.wolfram.com/CubicVertex-TransitiveGraph.html

-
Transitive means that the automorphism group of the graph acts transitively on the graph. (Wikipedia quote here.) Perhaps someone could shed some light on intuition about this? – Patrick Da Silva Feb 16 '12 at 3:55
The five cubic graphs on 8 vertices are here: imm.io/gDDQ – utdiscant Feb 16 '12 at 7:24
@GerryMyerson thanks for the mathworld link - it appears that the graph shown above is the 4-Mobius ladder graph and the one mentioned by Patrick is the Cubical graph. It's nice to know they have names! – Hooked Feb 16 '12 at 14:26