7.1. Basic definitions and theorems
Let us examine the following "forbidden subgraph" problems: At most how many edges are in a graph of order n which does not contain
- a path of length n ?
- a cycle of length at least (at most) l ?
- a
complete graph
?
independent edges ?
- a Kuratowsky graph ?
- etc...
Why are these problems extremal?
If for a given class of graphs a certain graph parameter, say the number of edges or the minimum degree, is at most some number f, then the graphs for which equality holds are extremal graphs of the inequality.
Usually, let denote the
extremal graph of order n which does not contain a given subgraph F,
then the graph has
edges.
Examples:
-
Let C denote an arbitrary cycle of a graph G with order n. Then
, since a graph order n contains at most
edges to remain acyclic.
-
If we are looking for the extremal graph which does contain
independent edges, then in
we have
.