# Examples of cubic graphs in which every cycle of length divisible by 3 has a chord

Cubic graphs (graphs in which every vertex has valency 3) cannot be trees, so they contain a lot of cycles. Some of these cycles have length divisible by 3 (e.g. triangles, hexagons, nonagons etc).

In a generic cubic graph some of these cycles will have chords (edges connecting non-adjacent vertices in the cycle) and some won't. My interest is in graph in which every cycle of length divisible by 3 has a chord. In particular such a graph can contain no triangles as these never have chords.

I constructed some examples, all of which were bipartite. However I don't see any natural reason why such a graph should necessarily be bipartite so my question is:

Does anyone know an example of a non-bipartite cubic graph in which every cycle of length divisible by 3 has a chord?

• Vincent-- My previous answer (if you read it) turned out to be equivalent to yours below. Please check out the edited version of my answer which contains a six vertex example. Thanks. – coffeemath May 7 '16 at 9:02

• Your graph is a prism graph with parameter 5 (i.e. two pentagons with corresponding vertices joined). It is not bipartite because it has a 5-cycle. It has $4$ 6-cycles containing any particular vertex, and each has a chord. – Robert Israel May 6 '16 at 23:18
• It also has $9$-cycles, but since removing a single vertex still leaves some $4$-cycles, all $9$-cycles have chords. So yes, this is really an example. – Robert Israel May 6 '16 at 23:31
• Sorry, that should be $3$ (unordered) $6$-cycles. Each $6$-cycle consists of two adjacent $4$-cycles formed by two adjacent sides of one pentagon, the corresponding sides of the other pentagon, and the edges joining them. – Robert Israel May 6 '16 at 23:48
• Moreover, seeing as it has $<12$ nodes, it can't possibly have an induced 9-cycle. This is another way to prove @RobertIsrael's statement. – Rosie F Feb 23 at 17:02