Graph Excision
Let a tree 
be a subgraph
of a cubic graph 
. The graph excision 
is the graph resulting from removing the tree, then merging the edges. For example,
if in the Levi graph (left figure) the tree formed
by the 6 interior points (middle figure) is excised, the McGee
graph (right figure) results. Similarly, excising the Heawood
graph gives the Petersen graph, and excising
the generalized hexagon (i.e., the unique
12-cage graph) gives the Balaban
11-cage (Biggs 1998).
The reverse of excision is insertion. Both operations are used in the analysis of cages.
The following table gives some cubic symmetric graphs with named edge-excised graphs, illustrated above.
| graph | edge-excised graph |
| utility graph | tetrahedral graph |
| cubical graph | 3-prism graph |
| Petersen graph | 4-Möbius ladder |
| Heawood graph | 12-cubic graph 84 |
| Möbius-Kantor graph | 14-cubic graph 503 |
| dodecahedral graph | cubic polyhedral graph Cp34 |
Contact the MathWorld Team
2 * 4 * 6 * ... * 36
