211.7 Contraction and minorsFig.1.7.4. A subdivision of K* viewed as an MK4Now that we have met all the standard relations between graphs.we can also define what it means to embed one graph in another. Basi-cally, an embedding of G in H is an injective map o:V(G)V(H) thatembeddingpreserves the kind of structure we are interested in. Thus, embeds Gin H 'as a subgraph' if it preserves the adjacency of vertices, and 'asan induced subgraph' if it preserves both adjacency and non-adjacency.If is defined on E(G) as well as on V(G) and maps the edges ryof G to independent paths in H between p(r) and p(y), it embeds Gin H 'as a topological minor'. Similarly, an embedding y of G in H asaminorwould beamapfromV(G)todisjoint connected vertex setsin H (rather than to single vertices) such that H has an edge betweenthe sets () and (y) whenever ry is an edge of G. Further variants arepossible; depending on the context, one may wish to define embeddingsasaspanningsubgraph',‘asaninduced minor'and so on in theobivousway.1.8 Euler toursAny mathematician who happens to find himself in the East Prussiancity of Konigsberg (and in the 18th century) will lose no time to follow thegreat Leonhard Euler's example and inquire about a round trip throughthe old city that traverses each of the bridges shown in Figure 1.8.1exactly once.Thus inspired.9 let us call a closed walk in a graph an Euler tour ifit traverses every edge of the graph exactly once. A graph is Eulerian ifEulerianitadmitsanEulertour(16.]Theorem 1.8.1. (Euler 1736)A connected graph is Eulerian if and only if every vertex has even degreeProof.The degree condition is clearly necessary: a vertex appearing ktimes in an Euler tour (or k+1 times, if it is the starting and finishingvertex and as such counted twice) must have degree 2k.9 Anyoneto whom suchinspirationseeaftercontemplatingms far-fetchedFigure 1.8.2, may seek consolation in the multigraph of Figure 1.10.1.1.7 Contraction and minors 21 Fig. 1.7.4. A subdivision of K4 viewed as an MK4 Now that we have met all the standard relations between graphs, we can also define what it means to embed one graph in another. Basi￾cally, an embedding of G in H is an injective map ϕ: V (G)→V (H) that embedding preserves the kind of structure we are interested in. Thus, ϕ embeds G in H ‘as a subgraph’ if it preserves the adjacency of vertices, and ‘as an induced subgraph’ if it preserves both adjacency and non-adjacency. If ϕ is defined on E(G) as well as on V (G) and maps the edges xy of G to independent paths in H between ϕ(x) and ϕ(y), it embeds G in H ‘as a topological minor’. Similarly, an embedding ϕ of G in H ‘as a minor’ would be a map from V (G) to disjoint connected vertex sets in H (rather than to single vertices) such that H has an edge between the sets ϕ(x) and ϕ(y) whenever xy is an edge of G. Further variants are possible; depending on the context, one may wish to define embeddings ‘as a spanning subgraph’, ‘as an induced minor’, and so on in the obivous way. 1.8 Euler tours Any mathematician who happens to find himself in the East Prussian city of K¨onigsberg (and in the 18th century) will lose no time to follow the great Leonhard Euler’s example and inquire about a round trip through the old city that traverses each of the bridges shown in Figure 1.8.1 exactly once. Thus inspired,9 let us call a closed walk in a graph an Euler tour if it traverses every edge of the graph exactly once. A graph is Eulerian if Eulerian it admits an Euler tour. Theorem 1.8.1. (Euler 1736) [ 2.1.5 ] [ 10.3.3 ] A connected graph is Eulerian if and only if every vertex has even degree. Proof . The degree condition is clearly necessary: a vertex appearing k times in an Euler tour (or k + 1 times, if it is the starting and finishing vertex and as such counted twice) must have degree 2k. 9 Anyone to whom such inspiration seems far-fetched, even after contemplating Figure 1.8.2, may seek consolation in the multigraph of Figure 1.10.1