Exercises 1. (2.1.10 BM-GTM244) Show that the incidence graph of a finite projective plane has girth six. - 2. (2.1.13 BM-GTM244) Let D be a strict digraph. Setting k max{8,6), show that: a) D contains a directed path of length at least k, b) if k> 0, then D contains a directed cycle of length at least k + 1. 3. (2.1.16 BM-GTM244) a) Show that if mn +4, then G contains two edge-disjoint cycles. b) For each integer n 5, find a graph with n vertices and n + 3 edges which does not contain two edge-disjoint cycles. 4. (2.2.2 BM-GTM244) a) Deduce from Theorem 2.4 that every loopless graph G contains a spanning bipartite subgraph F with e(F) > (G). b) Describe an algorithm for finding such a subgraph by first arranging the vertices in a linear order and then assigning them, one by one, to either X or Y, using a simple rule. 2.5.5, 2.6.2 5. (2.4.4 BM-GTM244) a) Show that K, can be decomposed into copies of K, only if n1 is divisible by pl and n(nl) is divisible by p(pl). For which integers n do these two conditions hold when p is a prime? b) For k a prime power, describe a decomposition of Kk2+k+1 into copies of Kk+1, based on a finite projective plane of order k. 6. (2.4.9 BM-GTM244) Give an alternative proof of the de Bruijn-Erds Theorem (see Exercise 1.3.15b) by proceeding as follows. Let M be the incidence matrix of a geometric configuration (P, L) which has at least two lines and in which any two points lie on exactly one line. a) Show that the columns of M span R", where n := IPI. b) Deduce that M has rank n. c) Conclude that |C|2|P|. 7. (2.5.5 BM-GTM244) An odd graph is one in which each vertex is of odd degree. Show that a graph G is odd if and only if |0(X)| = |X|(mod 2) for every subset X of V. 8. (2.6.2 BM-GTM244) Show that the edge space E(G) is a vector space over GF(2) with respect to the operation of symmetric difference, and that it is isomorphic to (GF(2))E. 1

Exercises 1. (2.1.10 BM-GTM244) Show that the incidence graph of a finite projective plane has girth six. 2. (2.1.13 BM-GTM244) Let D be a strict digraph. Setting k:=max{+}, show that: a) D contains a directed path of length at least k, b) if k>0, then D contains a directed cycle of length at least k+1. 3. (2.1.16 BM-GTM244) a) Show that if mn+4, then G contains two edge-disjoint cycles. b) For each integer n5, find a graph with n vertices and n+3 edges which does not contain two edge-disjoint cycles. 4. (2.2.2 BM-GTM244) a) Deduce from Theorem 2.4 that every loopless graph G contains a spanning bipartite subgraph F with e(F)2e(G). b) Describe an algorithm for finding such a subgraph by first arranging the vertices in a linear order and then assigning them, one by one, to either X or Y, using a simple rule. 2.5.5,2.6.2 5. (2.4.4 BM-GTM244) a) Show that Kn can be decomposed into copies of Kp only if n1 is divisible by p1 and n(n1) is divisible by p(p1). For which integers n do these two conditions hold when p is a prime? b) For k a prime power, describe a decomposition of Kk2+k+1 into copies of Kk+1, based on a finite projective plane of order k. 6. (2.4.9 BM-GTM244) Give an alternative proof of the de Bruijn-Erds Theorem (see Exercise 1.3.15b) by proceeding as follows. Let M be the incidence matrix of a geometric configuration (P,L) which has at least two lines and in which any two points lie on exactly one line. a) Show that the columns of MspanRn, where n:=P. b) Deduce that M has rank n. c) Conclude that LP. 7. (2.5.5 BM-GTM244) An odd graph is one in which each vertex is of odd degree. Show that a graph G is odd if and only if (X)X(mod2) for every subset X of V. 8. (2.6.2 BM-GTM244) Show that the edge space E(G) is a vector space over GF(2) with respect to the operation of symmetric difference, and that it is isomorphic to (GF(2))E