71.3 Paths and cyclesFig.1.3.1.ApathP=P6inGFor 0≤i<j≤ k we writeaPy,pPr,- ro....iaP:-ri..akaiPr, =Ti..tjandP:= T1...Tk-1Pa,.-o...T-1,P:=T+.Tki,Pi, =a+j-1for the appropriate subpaths of P. We use similar intuitive notation forthe concatenation of paths; for example, if the union PrUrQyUyR ofthree paths is again a path, we may simply denote it by PrQyR.PrQyRFig. 1.3.2. Paths P, Q and rPyQzGiven sets A, B of vertices, we call P = Zo...Tk an A-B path ifA-B pathV(P)nA = (ro} and V(P)n B = (]. As before, we write a-Binde-path rather than (a)-B path, etc. Two or more paths are independentpendentif none of them contains an inner vertex of another: Two a-b paths, forinstance, are independent if and only if a and b are their only commonvertices.Given a graph H, we call P an H-path if P is non-trivial and meetsH-pathH exactly in its ends. In particular, the edge of any H-path of length 1is never an edge of H.IfP= ro..Ck-1 is a path and k ≥ 3, then the graph C :P+ k-1to is called a cycle. As with paths, we often denote a cyclecycleby its (cyclic) sequence of vertices; the above cycle C might be written1.3 Paths and cycles 7 G P Fig. 1.3.1. A path P = P6 in G For 0 i j k we write xP y, P ˚ P xi := x0 ...xi xiP := xi ...xk xiP xj := xi ...xj and P ˚ := x1 ...xk−1 P˚xi := x0 ...xi−1 ˚xiP := xi+1 ...xk ˚xiP˚xj := xi+1 ...xj−1 for the appropriate subpaths of P. We use similar intuitive notation for the concatenation of paths; for example, if the union P x ∪ xQy ∪ yR of three paths is again a path, we may simply denote it by PxQyR. PxQyR x xP yQz y z x P y Q z Fig. 1.3.2. Paths P, Q and xP yQz Given sets A, B of vertices, we call P = x0 ...xk an A–B path if A–B path V (P) ∩ A = { x0 } and V (P) ∩ B = { xk }. As before, we write a–B path rather than { a }–B path, etc. Two or more paths are independent inde￾pendent if none of them contains an inner vertex of another. Two a–b paths, for instance, are independent if and only if a and b are their only common vertices. Given a graph H, we call P an H-path if P is non-trivial and meets H-path H exactly in its ends. In particular, the edge of any H-path of length 1 is never an edge of H. If P = x0 ...xk−1 is a path and k 3, then the graph C := P + xk−1x0 is called a cycle. As with paths, we often denote a cycle cycle by its (cyclic) sequence of vertices; the above cycle C might be written