Excluding long paths

الأصل · EN

Ding (1992) proved that for each integer m 0, and every infinite sequence of finite simple graphs G₁, G₂,, if none of these graphs contains a path of length m as a subgraph, then there are indices i < j such that Gᵢ is isomorphic to an induced subgraph of Gⱼ. We generalise this result to infinite graphs, possibly with parallel edges and loops.