A 1-factor, is a subgraph which includes every vertex and is regular of degree $1$. (Here we will use factor as an abbreviation for 1-factor; in some contexts people use the term factor to denote a spanning regular graph.) For $K_6$ a 1-factor is a collection of $3$ edges with no common vertices.

We build $K_6$ first. We will work with sets of sets, so we convert the edges of $K_6$ into two-element sets. Note that the vertices are integers, starting with zero. Also, we use the Sage constructor Set() rather than the Python version (set()), since these behave differently and we will have an easier time with the Sage version. Of course, $K_6$ has $6$ vertices and ${6\choose 2}=15$ edges. We will see these numbers repeatedly throughout this chapter.

xxxxxxxxxx

K6 = graphs.CompleteGraph(6)

vertices = K6.vertices()

vertices

xxxxxxxxxx

edges = [Set(e) for e in K6.edges(labels=False)]

edges

We will give each of the $15$ edges a name (an arbitrary lowercase letter) which will make some of our graphs a bit more tidy when displaying them. A Python dictionary (mapping) is a natural way to specify this.

xxxxxxxxxx

edge_names = dict(zip(edges, [chr(i) for i in range(ord('a'), ord('a')+15)]))

edge_names

Since $K_6$ includes every possible edge, a factor is partition of the vertex set into a set of three $2$-sets. We discover $15$ factors.

xxxxxxxxxx

factors = SetPartitions(vertices,[2,2,2]).list()

factors = [Set(list(A)) for A in factors]

factors

xxxxxxxxxx

len(factors)

We can easily visualize the $15$ different factors by considering each factor as an edge-induced subgraph of $K_6$. We build a list of these subgraphs and use a convenient utility in Sage to display them all simply and compactly. These $15$ objects will be critical in what follows.

xxxxxxxxxx

factor_graphs = [Graph([e.list() for e in f]) for f in factors]

graphs_list.show_graphs(factor_graphs)

The edge-factor incidence graph is a remarkable graph. The Tutte $8$-cage is the cubic graph (i.e. regular of degree $3$) with girth $8$ and having the fewest possible number of vertices. It therefore also qualifies as a Moore graph. Since it is distance-transitive, it is also distance-regular.

We use the set of edges and the set of factors as the vertex set of a graph. We join an edge to a factor if the edge is a component of the factor.

xxxxxxxxxx

T = Graph([(e, f) for e in edges for f in factors if e in f])

T.num_verts(), T.num_edges(), T.is_bipartite(), T.is_regular(), T.average_degree(), T.girth()

xxxxxxxxxx

T.is_isomorphic(graphs.TutteCoxeterGraph())

Since this graph is built into Sage, we can get a much more pleasing drawing from the embedding that is hard-coded. If we give our factors names (uppercase letters from the start of the alphabet), then we can relabel the vertices of a copy of the graph and use Sage's BipartiteGraph class to get another informative drawing.

xxxxxxxxxx

graphs.TutteCoxeterGraph().plot()

xxxxxxxxxx

factor_names = dict(zip(factors, [chr(i) for i in range(ord('A'), ord('a')+15)]))

factor_names

xxxxxxxxxx

TB = copy(T)

TB.relabel(edge_names)

TB.relabel(factor_names)

BipartiteGraph(TB).plot()