Mycielskian triangle preservation
ID: mycielskian-triangle-preservation
A finite simple graph 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 and two originals requires all three original edges , 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 : 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.
New to topics? Read the docs here!