Skip to main content

Posts

Showing posts from June, 2013

Tutte's Twist Operation on Cubic Graphs

There is an interesting book by W. T. Tutte  called ' Graph Theory as I have known it ' which is a cross between a normal mathematical text and a biography. So it's a description of the areas he was interested in, and his theorems. One thing that interested me was the use of a 'twist' operation on cubic graphs like so: Where for the edge between vertices x and y labelled 'A' we reconnect the surrounding edges to form the arrangement on the right hand side. So detach edge D from y and connect it to x, and vice versa with edge C. The lower part of the picture shows what happens for a loop-edge - it transforms to a multi-edge. This operation is used on a family of 'base' graphs looking like this: with the first in the list is a vertexless loop graph - that is, it has no vertices and a single edge. From these base graphs, the twist operation can form any cubic graph. Note that all of U n are cubic with 2n vertices. For example, from U 3 we