Forbidden subgraph

Forbidden subgraph --- запрещенный подграф.

1. If [math]\displaystyle{ H_{1}, \ldots, H_{k} \; (k \geq 1) }[/math] are graphs, then a graph [math]\displaystyle{ G }[/math] is said to be [math]\displaystyle{ H_{1}, \ldots, H_{k} }[/math]-free if [math]\displaystyle{ G }[/math] contains no copy of any of the graphs [math]\displaystyle{ H_{1}, \ldots, H_{k} }[/math] as an induced subgraph; the graphs [math]\displaystyle{ H_{1}, \ldots, H_{k} }[/math] will be also referred to in this context as forbidden subgraphs.

2. A cf-graph [math]\displaystyle{ G }[/math] with the initial node [math]\displaystyle{ p_0 }[/math] has a forbidden subgraph if there exist distinct nodes [math]\displaystyle{ p_1 }[/math],[math]\displaystyle{ p_2 }[/math] and [math]\displaystyle{ p_3 }[/math] and simple paths [math]\displaystyle{ P_{0,1} }[/math], [math]\displaystyle{ P_{1,2} }[/math], [math]\displaystyle{ P_{1,3} }[/math], [math]\displaystyle{ P_{2,3} }[/math], [math]\displaystyle{ P_{3,2} }[/math], where [math]\displaystyle{ P_{i,j} }[/math] denotes a path from [math]\displaystyle{ p_i }[/math] to [math]\displaystyle{ p_j }[/math], that do not intersect on internal nodes.