This assignment concerns the following view of a decomposition of a graph G:

• Select a subset X of vertices of G, and complement the edges induced by X in G. Precisely, a new graph G' is constructed on the same vertex set, such that {u,v} is an edge of G' if, and only if, at least one of u,v is not in X and {u,v} is an edge of G, or both u,v are in X and {u,v} is not an edge of G.
• Decompose the new graph G' into its connected components, and apply the previous point onto each component recursively (in parallel). Stop when the component is a single vertex (no edge).

The depth of the graph G is then defined as the lowest possible depth of this recursive construction of G. In other words, if H₁,...,H_k are the connected components of the graph obtained by complementing edges of G on a subset X of vertices, then recursively  depth(G)= 1+ min_X [ max(depth(H₁),...,depth(H_k)) ]  (where the minimum is taken over all subsets X of the vertex set of G). The base case is depth(v)=0.

You task is to examine which graphs have "high" depth (depedending on their number of vertices):

1. For start, prove that the depth of a path of length n is growing with n. How good lower and upper estimates on depth(P_n) can you get?
2. Show also the relation between the depth of G and of the complement of G (where edges on all vertices are complemented).
3. The main question is to find a sequence of graphs which contain neither arbitrarily long induced paths nor their complements, but whose depth grows to infinity. If you get one such sequence, do not stop but try to find another, substantially different one (you may then get more points).
4. Could you, by chance, asymptotically describe all the graphs which have depth bounded by some (arbitrary) constant <=D ?
   By asymptotically we mean something like this, say: All the graphs of depth <=10 have "this nice shape", and all graphs that have "this nice shape" are of depth <=10000... For instance, a sequence of trees has bounded depth iff these trees have bounded diameter. Is there a similar description among all graphs? (This point may be worth many bonus points, but also solutions without this point will be considered.)

Do not hesitate to ask for details in the IS discussion.

Good luck...

Read the general remarks in parent section!