# Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$ [duplicate]

This question already has an answer here:

Knowing every odd circuit in a graph is a triangle, prove $$\chi(G) \le 4$$

My approach: an odd circuit requires 3 colors, and an even circuit requires 2. But then I'm stuck. Can you give me a hint on how to proceed? No complete solution please.

## marked as duplicate by Misha Lavrov graph-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 20 at 3:50

If you're familiar with 2-connected graphs, then you can use the following strategy.

First, whenever $$v$$ is a cut vertex of $$G$$, we can divide up $$G$$ into fragments $$G_1, G_2, \dots, G_k$$ whose union is $$G$$, such that they all contain $$v$$ but are otherwise disjoint. We can color $$G_1, G_2, \dots, G_k$$ individually, then combine the colorings.

This leaves as a base case graphs which are $$2$$-connected and don't have a cut vertex. With the condition that all cycles in the graph are triangles, you can narrow down the possibilities and then say how to color all of these.

Actually, I believe that you should be able to prove that $$\chi(G) \le 3$$ for all such graphs.

• Thanks! I think I know what to do. – Kai May 19 at 23:14
• I changed the question. – Kai May 20 at 3:33
• The same strategy should work; there are now several possible 2-connected graphs instead of one, but they are all either bipartite or subgraphs of $K_4$. – Misha Lavrov May 20 at 3:52

Hint:

Any such graph will look like a tree with some vertices blown up into triangles (or alternatively, identify the vertices of each triangle in your graph and show that this is a tree). Prove this, and show that any such graph $$G$$ has $$\chi(G)\le 3$$.