What properties does a graph $G$ which does not have a triangle-free Euler circuit have?

84 Views Asked by At

An Euler circuit $v_1,v_2,v_3,\dots,v_n,v_1$ is a triangle-free Euler circuit if and only if there do not exist four consecutive nodes $v_i,v_{i+1},v_{i+2},v_{i+3}$ with $v_i = v_{i+3}$.

Now what are the properties of a graph which does not have such an Euler circuit; i.e., every Euler circuit has a triangle in it.

For example, it is not a bipartite graph.