Answer to Problem 12

These are the graphs that don't have cycles of length three (in other words, graphs that don't contain triangles). Indeed, if in a graph the degree of a vertex is , and and are two vertices adjacent to , then the vertex-edge-vertex-edge-vertex sequence



Equation 1

is a path of length two. Since this path is supposed to be an induced subgraph, and are not adjacent.

This is equivalent to saying that has no 3-cycles.