Forbidden induced path
Task number: 3601
Find all graphs that contain no induced path of length \(2\).
As in the previous exercise we may restrict ourselves to connected components.
A complete graph cannot contain an induced path of length \(2\), i.e. an induced subgraph \(P_3\), because every triple of vertices induces \(K_3\), not \(P_3\).
There cannot be any components that are not complete. If a connected graph is not complete, it contains two vertices \(u\) and \(v\) at a distance of at least two. Then the first three vertices in the shortest path from \(u\) to \(v\) determine the induced path \(P_3\).
The graphs without an induced path \(P_3\) are disjoint unions of complete graphs.