Forbidden induced path

Task number: 3601

Find all graphs that contain no induced path of length \(2\).

  • Solution

    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\).

  • Answer

    The graphs without an induced path \(P_3\) are disjoint unions of complete graphs.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email