The following graphs are motivated by the Erdos/Gyarfas conjecture
which asserts (more or less)
that every graph with minimum degree at least 3 has a cycle whose
length is a power of 2.
|
A smallest trivalent graph with no 4, 6, or 10 cycles.
|
|
A trivalent graph of order 32 with no 4, 8 or 32 cycles.
|
|
A smallest trivalent graph with no 4 or 8 cycles (there are 3 others)
|
|
Another example of a graph with no cycles of lengths 4 and 8.
|
|
The (unique) smallest trivalent graph with no 4 or 6 cycles.
|
|
A smallest trivalent graph with no 4, 6 or 8 cycles.
|
The smallest graph I know of with no 4, 8 or 16 cycles
has 78 vertices. The smallest with no 4, 8, 16 or 32 cycles
has 540 vertices. I'd be interested to hear of any smaller
examples.