1
$\begingroup$

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:

vertex_tran_8_3

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

  • 0
    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.2016-02-24

2 Answers 2

2

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,

  • 1
    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.2012-02-16
2

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

  • 1
    @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!2012-02-16