= Mycielskian triangle preservation
{c}
A finite <simple graph> $G$ is a <triangle-free graph> if and only if its <Mycielskian> is a <triangle-free graph>. No <triangle in a graph> can contain the <Mycielski apex>, whose neighbours are an <independent set>, or two <Mycielski shadow vertices>. A <triangle in a graph> containing one shadow $u_i$ and two originals $v_j,v_\ell$ requires all three original <edges> $v_iv_j,v_iv_\ell,v_jv_\ell$, hence an original <triangle in a graph>. Conversely every original <triangle in a graph> remains. In fact each original <triangle in a graph> gives four in $\mu(G)$: itself and the three choices of replacing one of its <vertices> by its shadow. Thus triangle-freeness is preserved, but a positive <triangle count> is multiplied by four.
Back to article page
