Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
As the title says, I have a simple finite graph whose every odd cycle is a triangle, and I want to show that $\chi (G)\leq 4$.
My idea was trying to use the fact that a graph is bipartite iff it contains no odd cycles. The general direction was: if we somehow "remove" the triangles, we get a 2-colorable graph, and then maybe somehow we can add them back without adding more that 2 colors needed...?
Let $G=(V,E)$ be a finite graph in which every odd cycle is a triangle. We can assume that $G$ is a minimal counterexample, so that every proper subgraph of $G$ is $4$-colorable, and $G$ is a connected simple graph. Choose a root vertex $u.$
Let $V_i=\{v\in V:d(u,v)\equiv i\pmod2\}.$ If both of the induced subgraphs $G|V_1$ and $G|V_2$ are $2$-colorable, we're done; so we can assume that one of them contains an odd cycle, which must be a triangle. That is, $G$ contains a triangle $T$ with $V(T)=\{v_1,v_2,v_3\}$ where $d(u,v_1),\ $$d(u,v_2),$ and $d(u,v_3)$ all have the same parity.
Note that $u\notin V(T),$ and a shortest path from $u$ to $v_i$ contains no edge or vertex of $T$ except $v_i.$ Hence there is a path $P$ from $v_1$ to $v_2$ which contains no edge or vertex of $T$ except $v_1$ and $v_2.$ The path $P$ must have length $\ge2,$ but if $P$ had length $\ge3$ then by adding one or two edges of $T$ to it we would get an odd cycle of length $\ge5,$ so the length of $P$ is exactly $2.$ That is, there is a vertex $w\notin V(T)$ which is adjacent to $v_1$ and $v_2.$
By the same token, there is a vertex $w'\notin V(T)$ which is adjacent to $v_2$ and $v_3.$ But if we had $w\ne w'$ then we would have a $5$-cycle $v_1,w,v_2,w',v_3,v_1$ in $G.$ Therefore $w=w'$ is adjacent to all three vertices in $V(T).$ Let $v_4=w=w';$ then the induced subgraph $Q=G|\{v_1,v_2,v_3,v_4\}$ is a $K_4.$
The spanning subgraph $G'=G-E(Q)$ is $4$-colorable. Note that the vertices $v_1,v_2,v_3,v_4$ lie in four different components of $G';$ for, if $v_i$ and $v_j$ ($i\ne j$) were connected by a path in $G',$ then there would be an odd cycle of length $\ge5$ in $G.$ Therefore, in $4$-coloring $G',$ the colors of those four vertices can be assigned arbitrarily; we give them different colors, so that the coloring of $G'$ will also be a proper coloring of $G.$
This argument shows that a finite graph, in which every odd cycle is a triangle, is $4$-colorable. By the Erdős–De Bruijn theorem, the same goes for infinite graphs.
