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.