Exercise 5, § 2

a) Let $n$ be a natural number $\geqslant 1$ and let G be a graph whose set of vertices is the set $\mathbf{Z}/n\mathbf{Z}$ and such that two vertices $i$ and $j$ are joined by an arrow if and only if $i-j=\pm 1$ (mod$. n$). Make explicit the set of maximal forests of G.

b) Let G be a graph and let S be the set of its vertices. Suppose that for every pair $(x, y)$ of vertices of G, the set of arrows of G with origin $x$ and term $y$ has cardinal 1 if $x=\not y$ and 0 otherwise ("complete graph"). Calculate the cardinal of the set of maximal forests of G.

c) Let G be a graph and let S be the set of its vertices. Let $(S_1,S_2)$ be a partition of S; suppose that for every pair $(x, y)$ of vertices of G, the set of arrows of G with origin $x$ and term $y$ has cardinal 1 if $(x, y)\in S_1\times S_2$ and 0 otherwise ("complete bipartite graph"). Calculate the cardinal of the set of maximal forests of G.