If is a given partial order on I, then the set of all -hereditary properties will be denoted by . As special cases the set of all hereditary properties will be denoted by and the set of all additive hereditary properties will be denoted by ^a. The first results in this section describe the structure of these sets, ordered by inclusion.

Theorem 1 ([17]) The partially ordered sets (, ) and (^a, ) are distributive lattices.

Note that is closed under (arbitrary) intersections and unions while ^a is closed under (arbitrary) intersections. Hence the properties in and in ^a form closure systems (see [3]). From this it follows that the lattices in Theorem 1 are complete. Hence we have

Theorem 2 [17] The partially ordered sets (, ) and (^a, ) are complete distributive lattices with least element and greatest element I.

It should be noted that (^a , ) is not a sublattice of ( , ) since the join of properties in the former is not the union of these properties. Therefore the distributivity of (^a, ) is not completely trivial. In [17], [70] an isomorphism between (^a, ) and a suitable lattice of sets of connected graphs is used to prove it.

For a graph HI, H denotes the class of all graphs that admit homomorphisms to H. Such classes of graphs are called hom-properties or colour classes and were investigated e.g., in [55], [61], [62], [77] and [102]. It was pointed out that they play an interesting role in the lattice (^a,).

Theorem 3 [60] The hom-properties form a sublattice of ^a.

We will present more information about the structure of the sublattice of hom-properties in Section 3.

For a given nonnegative integer k, let

_k^a = { P ^a : c(P) = k }.

Since _k^a is also a closure system we have

Theorem 4[17] The ordered set (_k^a , ) is a complete distributive lattice and it is a sublattice of (^a , ). O_k is the least element and I_k is the greatest element of (_k^a , ).

Since the set forms a lattice with a set union and a set intersection as operations it is natural to ask, for any two hereditary properties P₁ and P₂, what the completeness of P₁ P₂ and P₁ P₂ is in terms of the completenesses of P₁ and P₂. Our next result answers this question.

Theorem 5[17]
Let P₁ and P₂ be any nontrivial hereditary properties of graphs. Then c(P₁ P₂) = max{c(P₁), c(P₂)} and c(P₁ P₂) = min{c(P₁), c(P₂)}.

The algebraicity of these lattices will be discussed in Section 4.

2.1 Minimal Forbidden Subgraphs

F(P)= {G I : G P but each proper subgraph H of G belongs to P}.

Note that F(P) may be finite or infinite.

Some direct consequences of this definition are contained in the next lemma. It shows amongst others how a hereditary property can uniquely be determined by its set of minimal forbidden subgraphs.

Lemma 6. Let P be a hereditary property. Then
(a) G P if and only if no subgraph of G is in F(P).
(b) If P is additive, then F(P) contains only connected graphs.

The set of minimal forbidden subgraphs of each of the properties in Example 1, except for D_k and hom-properties, is easy to describe. A list of them is given in the following example.

Example 2. Let S_n and P_n to denote the star and the path on n vertices, respectively. Then

F(O)	=	{ K2 },
F(Ok)	=	{H I : H is a tree on k+2 vertices},
F(Sk)	=	{Sk+2},
F(Wk)	=	{Pk+2},
F(Tk)	=	{H I : H is homeomorphic to Kk+2 or K},
F(Ik)	=	{Kk+2}.

To characterize the set F(D_k) we need some more notation. For a nonnegative integer k and a graph G, we denote the set of all vertices of G of degree k+1 by M(G). If S V(G) is a cutset of vertices of G and G₁, . . . ,G_s, s2 are the components of G - S, then the graph G - V(G_i) is denoted by H_i, i=1, . . . ,s.

Theorem 7[67] A graph G belongs to F(D_k) if and only if G is connected, (G) k+1, V(G) - M(G) is an independent set of vertices of G and for each cutset SV(G) - M(G) we have that (H_i) k for each i=1, . . . ,s.

The characterization of the the forbidden graphs for a hom-property H seems to be very complicated and it is known just for very particular choices of the graph H (see [62]). Such choices of the graph H yields to the properties which were already discussed in Example 2.

In the next theorem the following notation is useful. If S is a set of graphs we write min[S] for the set of graphs in S that are minimal with respect to the partial order on I. Note that, in this notation, F(P) = min [I - P] for any nontrivial hereditary property P.

Theorem 8[17] Let P₁ and P₂ be any nontrivial hereditary properties of graphs. Then

1. F(P₁ P₂) = min [F(P₁) F(P₂)],
2. F(P₁ P₂) = min [H I : there exists a pair of graphs G₁ F(P₁) and G₂ F(P₂) such that G₁ H and G₂ H }].

The completeness of a property is now described in terms of its forbidden subgraphs.

Theorem 9[17] Let P be any nontrivial hereditary property of graphs. Then c(P)= min{|V(H)|-2 : H F(P)}.

Inclusion between properties, and hence equality between properties, can also be described in terms of forbidden subgraphs.

Theorem 10[17] Let P₁ and P₂ be any nontrivial hereditary properties. Then P₁ P₂ if and only if for every H F(P₂) there exists a graph H' F(P₁) such that H' H.

2.2 P-maximal Graphs

M(P) = {G I : G P G + e P for each e E()}

and the set of P-maximal graphs of order n by

M(n,P) = {G I : G P, G+e P for each eE() and |V(G)| = n}.

Our next result follows immediately from these definitions.

Lemma 11. Let P be a nontrivial hereditary property. Then

1. A graph G belongs to P if and only if there exists a graph H M(P) such that GH.
2. A graph G of order n belongs to P if and only if there exists a graph H M(P)n such that GH.
3. M(P) = _n M(n,P).
4. If a graph G belongs to M(P) then every component of G belongs to M(P).

From the definition of P-maximal graphs and the completeness of a property we immediately deduce the following result.

Lemma 12. [21] Let P be a nontrivial hereditary property. Then

1. M(n,P) = {K_n} for each n with 1 n c(P) + 1.
2. If G M(P), H M(P) and G is a subgraph of H or H is a subgraph of G, then G = H.

It is natural, that Statement 2 of the previous lemma inspire us to introduce a more general concept---the generator of a hereditary (an additive hereditary) property. To be more exact, consider an arbitrary set X, a subset of I. It is quite easy to see,that the property

[X]={G I : G is a subgraph of some graph H X}

is hereditary, the property

[X]^a={G I : each component of G is a subgraph of some H X}

is in addition additive and both are generated by the set X, called generator.

The previous lemma yields, that the set M(P) generates the (additive) hereditary property P. On the other hand, it is not difficult to see, that the set M(P) is neither the unique nor the minimal (with respect to the set inclusion) generator of P. In fact, for any positive integer k the sets M_k=_nk M(n,P) and M^*_k= _nk,n0(mod2) M(n,P) are generators of P too. The concept of generator will be discussed, in more details and in general, with respect to a partial order, in Section 4.

From the definitions follows, that there is a very strong dependence between the structure of minimal graphs and the structure of P-maximal graphs for a given hereditary property P. One can expect, that it is quite easy to deduce the structure of forbidden graphs when all P-maximal graphs are known and vice versa. Unfortunately, this problem seems to be very difficult even for such familiar hereditary properties as O² (to be a bipartite graph) and D₁ (to be a forest). Indeed, although the structure of the sets F(O²), F(D₁), M(O²) and M(D₁) is well described, there are known no general rules, which can be used for a transformation between F(O²) and M(O²), and F(D₁) and M(D₁).

However, the dependence can be expressed by means of a graph theoretical invariant. In order to present it, we need the following notation. If is any graph theoretical invariant, then the symbol (P) stands for

(P)= min{(F):F F(P)}.

Theorem 13[72] Let (G) be a graph theoretical invariant satisfying:

1. for each subgraph H of G the value (H) is at most (G),
2. for any graph G I and for an arbitrary edge e from the complement of G holds (G+e) (G)+1.

Then for any graph G M(n,P) with n c(P)+ 2 holds the following:
(G) (P)-1.

The next lemma shows that inclusion between properties can also be described in terms of the corresponding sets of maximal graphs.

Lemma 14[21] Let P₁ and P₂ be any nontrivial hereditary properties. Then P₁ P₂ if and only if for every G M(P₁) there is a graph H M(P₂) such that G H.

The next lemma provides a criterion for the verification of P-maximal graphs in terms of the features of comparable hereditary properties.

Lemma 15[84] Let P₁ and P₂ be any hereditary properties of graphs. If P₁ P₂, G M(n,P₂) and G P₁, then G belongs to M(n,P₁).

We now discuss the maximal graphs of order n for some of the properties listed in Example 1. In view of Lemma 12 we can restrict our attention to a property P and an integer n with n c(P) + 2. This is then our choice in each case of the following example.

Example 3. Let n be a positive integer, n c(P) + 2. Then

M(n,O)	=	{n},
M(n,Ok)	=	{Kr1} ... Krs:ri = n and ri+rj k+2, ri k+1 for each 1i,j s, i j} ,
M(n,{S}k)	=	{G I : (G) k , G is of order n and for every pair} of nonadjacent vertices of G at least one has degree k},
M(n,D1)	=	{GI : G is a tree of order n},
M(n,T2)	=	{GI : G is a triangulation of order n of the disc with no inner vertices},
M(n,T3)	=	{GI : G is a triangulation of order n of the plane},
M(n,I1)	=	{GI : G is a triangle-free graph of order n and every pair of non-adjacent vertices of G are at distance 2}.

The structure of maximal k-degenerate graphs has been studied extensively in [37], [64] and [75] and one description is given in the following theorem.

Theorem 16[64] Let G=(V,E) be a graph of order n, n k+1, and v V be a vertex of degree k. Then G M(n,D_k) if and only if G-v M(n-1,D_k).

The degree sequences of maximal k-degenerate graphs can also be characterized (see [15]). The characterization of graphs maximal with respect to hom-properties was obtained in [62] and will be presented in the Section 3.

We now introduce the notation max[ S], for a set S of graphs, to denote the set of graphs in S that are maximal with respect to the partial order on I. This concept is useful to describe M(n,P₁ P₂) and M(n,P₁ P₂) in terms of M(n,P₁) and M(n,P₂).

Theorem 17[84] Let n be a positive integer and let P₁ and P₂ be hereditary properties of graphs. Then

1. M(n,P₁ P₂) = max [M(n,P₁) M(n,P₂)],
2. M(n,P₁ P₂) = max [{G I : there exists a pair of graphs H₁ M(n,P₁) and H₂ M(n,P₂) such that G H₁ and G H₂,}].

2.3 Extremal Graph Problems

A general extremal problem, in our terminology, can be formulated as follows. Given a hereditary property P with a family F(P) of forbidden subgraphs, find the numbers

ex(n,P) = max{|E(G)|:G M(n,P)},
sat(n,P) = min{|E(G)|:G M(n,P)}.

The set of all P-maximal graphs of order n with exactly ex(n,P) edges is denoted by Ex(n,P). The members of Ex(n,P) are called P-extremal graphs. By the symbol Sat(n,P) we shall denote the set of all P-maximal graphs on n vertices with sat(n,P) edges. These graphs are called P-saturated.

A problem of such type was first formulated by Turán (see [95],[96]) and his original problem asked for the maximum number of edges in any graph of order n which does not contain the complete graph K_p (i.e. he was interested in the number ex(n,I_p-2)).

The following two theorems belong to the fundamental results of extremal graph theory.

Theorem 18[88] If P is a hereditary property with chromatic number (P), then

Theorem 19[58] If P is a given hereditary property and

u = u(P) = min{|V(F)|- (F)-1 : F P}

d = d(P) = min{|E(F')| F' F F(P) is induced by a set S{x}, S V(F) is independent and |S|=|V(F)|-u-1, x V(F)-S},

then

sat(n,P) un + (¹/₂)(d-1)(n-u)- ,

As a consequence of the previous two theorems we immediately have

Corollary 20. If P is a hereditary property of graphs and sat(n,P)=ex(n,P) for every positive n, then (P)=2.

The hereditary properties with (P)=2 are called degenerate. It will turn out in the next sections that these properties play an important role in the lattice ^a. We shall also deal with degenerate hereditary properties, which have some tree among forbidden subgraphs. As they position in the investigated lattice is also interesting, we shall called them very degenerate - see [89].

The numbers ex(n,P) and sat(n,P) have been studied very extensively e.g., in [34], [35], [58], [80], [86], [87], [88], [97], and [84], but there are not many hereditary properties, for which the exact values of sat(n,P) and ex(n,P) are known. It seems that the determination of sat(n,P) is much more complicated than the estimation of the number ex(n,P). There are two important causes for this fact. Firstly, unlike the number ex(n,P), the behaviour of sat(n,P) is not monotone in general (see [58]). Secondly, the determination of ex(n,P) requires max-max optimization, while for the evaluation of sat(n,P) the min-max type of optimization is necessary.

It was pointed out that the language of the lattice of hereditary properties enables us to investigate the numbers ex(n,P) and sat(n,P) from another point of view and utilize the structure of the lattice instead of the concrete knowledge about P-maximal graphs (for more details see [84]).

The following assertions present some results of utilization of this method.

Theorem 21([84]) If P is a hereditary property, such that O_k P D_k or D_k P I_k, n k+1, then sat(n,P) kn - .

Theorem 22([84]) Let P be a hereditary property and let D₁ P I₁. If the vertex-connectivity (P) 1, then sat(n,P)=n-1.