181.The Basics(1.5.1)Proof. Let G = (V, E) be a graph without odd cycles: we show that G isbipartite. Clearly a graph is bipartite if all its components are bipartiteor trivial, so we may assume that G is connected. Let T be a spanningtree in G, pick a root r e T, and denote the associated tree-order on Vby <T. For each u e V, the unique path rTu has odd or even length.This defines a bipartition of V; we show that G is bipartite with thispartition.Fig. 1.6.3. The cycle Ce in T+Let e = ay be an edge of G. If e e T, with z <T y say, thenrTy = rTry and so r and y lie in different partition classes. If e Tthen Ce := rTy + e is a cycle (Fig. 1.6.3), and by the case treatedalready the vertices along rTy alternate between the two classes. SinceCe is even by assumption, r and y again lie in different classes.口1.7 Contraction and minorsIn Section 1.1 we saw two fundamental containment relations betweengraphs: the'subgraph' relation, and the‘induced subgraph'relation. Inthis section we meet two more: the 'minor' relation, and the 'topologicalminor' relation.G/eLet e = ry be an edge of a graph G = (V, E). By G/e we denote thecontraction graph obtained from G by contracting the edge e into a new vertex ve,which becomes adjacent to all the former neighbours of r and of y. For-mally, G/eis a graph (V',E') with vertex set V':-(V<(,y))U(ve)(where ve is the 'new' vertex, i.e. ve VUE) and edge setUeE' :- [oweEl(u,w]n(r,y] =0]U vew l aweE-fe] or yw eE[e]]18 1. The Basics (1.5.1) Proof . Let G = (V,E) be a graph without odd cycles; we show that G is bipartite. Clearly a graph is bipartite if all its components are bipartite or trivial, so we may assume that G is connected. Let T be a spanning tree in G, pick a root r ∈ T, and denote the associated tree-order on V by T . For each v ∈ V , the unique path rTv has odd or even length. This defines a bipartition of V ; we show that G is bipartite with this partition. e Ce r x y Fig. 1.6.3. The cycle Ce in T + e Let e = xy be an edge of G. If e ∈ T, with x <T y say, then rTy = rT xy and so x and y lie in different partition classes. If e /∈ T then Ce := xT y + e is a cycle (Fig. 1.6.3), and by the case treated already the vertices along xT y alternate between the two classes. Since Ce is even by assumption, x and y again lie in different classes.
1.7 Contraction and minors In Section 1.1 we saw two fundamental containment relations between graphs: the ‘subgraph’ relation, and the ‘induced subgraph’ relation. In this section we meet two more: the ‘minor’ relation, and the ‘topological minor’ relation. G/e Let e = xy be an edge of a graph G = (V,E). By G/e we denote the contraction graph obtained from G by contracting the edge e into a new vertex ve, which becomes adjacent to all the former neighbours of x and of y. For￾mally, G/e is a graph (V , E ) with vertex set V := (V
{ x, y })∪ { ve } ve (where ve is the ‘new’ vertex, i.e. ve ∈/ V ∪ E) and edge set E := vw ∈ E | { v, w }∩{ x, y } = ∅  ∪ vew | xw ∈ E
{ e } or yw ∈ E
{ e }  .