Forbidden subgraphs
Task number: 3600
Find all subgraphs that contain no subgraphs of the following form:
Variant
Paths of length \(2\).
Hint
Restrict yourself to connected graphs.
Solution
If any component contains a forbidden subgraph, that subgraph must exist in the entire graph.
Because forbidden subgraphs are connected, if any graph contains one, it must be found in a single connected component.
From this argument it follows that if \(G\) must not contain any forbidden connected graph, \(G\) must be a disjoint union of connected graphs (komponents) which themselves do not contain any forbidden graph.
The connected graphs without paths of length \(2\) (we denote such paths according to the number of vertices \(P_3\)) are only \(K_1\) and \(K_2\). An arbitrary connected graph with at least three vertices contains some connected graph on three vertices and there are only two of those: \(P_3\) and \(C_3\). The first of these is forbidden and we can derive a forbidden graph from the second by removing any edge.
Answer
Graphs without a path of length \(2\) are disjoint unions of \(K_1\) and \(K_2\).
Variant
Paths of length \(3\).
Solution
Components of \(G\) may be \(K_1\), \(K_2\), \(K_3\) or \(K_{1,k}\).
The first three of these contain no four-vertex path of length 3 (denoted by \(P_4\)) since they have fewer than four vertices.
Subgraphs of the stars \(K_{1,k}\) are smaller stars and graphs without edges, none of which can be \(P_4\).
If \(G\) has any component\ other than those listed, that component must have at least four vertices (all smaller graphs are in our list).
If that component contains two vertices \(u\) and \(v\) at a distance greater than two, then the first four vertices of the shortest path from \(u\) to \(v\) give the forbidden subgraph \(P_4\). Otherwise this compmonent must have arisen by adding at least one edge to \(K_{1,k}\) with \(k\ge 3\). We can find the forbidden \(P_4\) by first taking this added edge, then the edge to the central vertex and then extending the path to some unused vertex (which must exist since \(k\ge 3\)).
Answer
Graphs without a path of length \(3\) are disjoint unions of \(K_1\), \(K_2\), \(K_3\) and \(K_{1,k}\).
Variant
Even cycles.
Answer
Graphs without even cycles can be derived from forests (i.e. graphs without cycles) by adding additional edges such that each additional edge adds at most one cycle, which must be of odd length.
In other words, there must exist at most one path between the ends of an additional edge (i.e. they may not lie on a cycle) and this path, if it exists, must have even length.
The graph may not have two odd cycles that share an edge – the symmetric difference of their sets of edges would give an even cycle.
