1.3Paths and cycleFig. 1.3.1. A path P = pe in Giting, say, P = rozi -.. h and calling P a path from ro to rx (as wellras between to and k)For 0≤i≤j<k we writeaPy,PPa,= To...a,P:=....kE,PajTi.TandDPi, = .-2,P:=Li+...Iki,Pi=Ti+1-.T-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.PaQyRFig. 1.3.2. Paths P, Q and rPyQzGiven sets A, B of vertices, we call P =Co..rkanA-BpathifA-BpathV(P)nA= (zo) and V(P)nB - (rk), As before, we write a-B pathpeadtrather than (aj-B path, etc.Two or more paths are independent ifnone 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 commonverticesGiven a graph H, we call P an H-path if P is non-trivial and meetsH-pathHexactlynitsendsInparticular,theedgeofanyH-pathoflengthis never an edge of H.1.3 Paths and cycles 7 G P Fig. 1.3.1. A path P = P6 in G writing, say, P = x0x1 ...xk and calling P a path from x0 to xk (as well as between x0 and xk). 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 P xQyR. P xQyR 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 if inde￾pendent 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.