Section2.1EulerCycles

1、Section 2.1Euler CyclesVocabularyCYCLE a sequence of consecutively linked edges (x1,x2),(x2,x3),(xn-1,xn) whose starting vertex is the ending vertex (x1 = xn) and in which no edge can appear more than once. No edge can appear more than once.EULER CYCLE a cycle that contains all the edges in a graph

2、(and visits each vertex at least once).TRAIL a sequence of consecutively linked edges in which no edge can appear more than once.MULTIGRAPHS a graph which permits several edges joining the same pair of vertices.bacdEx.1Exampleabcdefgmlhkonji(a)(b)Euler cycle: a,d,c,i,j,n,o,k,j,d,e,k,l,h,m,g,h,f,e,b,

3、acdeijkhgmfl2EULER TRAIL a trail that contains all the edges in a graph (and visits each vertex at least once).DEADHEADING EDGE edges added to a graph.LINE GRAPH The line graph L(G) of graph of G has a vertex for each edge of G,and two of these vertices are adjacent if and only if the corresponding

4、edges in G have a common end vertex.Ex.1235621536GL(G)3Origin of The Euler CycleThe Seven Bridges of KonigsbergBACDABCD4TheoremAn undirected multigraph has an Euler cycle if and only if it is connected and has all the vertices of even degree.PROOF: Suppose a multigraph G satisfies the two given cond

5、itions. Pick any vertex a and trace out a trail. Let C by the cycle thus generated and let G be the multigraph consisting of the remaining edges G-C.abcdefgmlhkonjicdeijkhgmfl(G)(G)Red = cycle C5Because the original path was connected, C and G must have a common vertex, call it a. Build a new cycle

6、C tracing through G from a just as C was traced in G from a. Incorporate C into the cycle C at a to obtain a new and larger cycle C. Repeat this process by tracing a cycle in the graph of G of still remaining edges and incorporate the cycle into C to obtain C. Continue until no edges remain. It must

7、 next be shown that if a Euler cycle exists, then the graph is connected and has all vertices of even degree. () In the essence of time we will save this for another day.cdeijkhgmflGreen = cycle CBlue = cycle CabcdefghijklmnoG = C + C + C6CorollaryA multigraph has an Euler trail, but not and Euler c

8、ycle, if and only if it is connected and has exactly two vertices of odd degree.PROOF: Suppose a multigraph has an Euler trail T, but not an Euler cycle. The starting and ending vertices of T must have odd degree while all other vertices have an even degree. Also the graph must be connected.Ex.7 Sup

9、pose on the other hand that a multigraph G is connected and has exactly two vertices, p and q, of odd degree. Add a supplementary edge (p,q) to G to obtain a graph G.pq G now has all vertices of even degree and therefore has an Euler cycle (Euler cycle theorem). Remove the edge (p,q) from C. Without

10、 this edge C the Euler cycle is reduced to an Euler trail that includes all of edges of G. Hence the corollary.8K2K3K4K5K6K8K2: Euler trail Yes Euler cycle NoK3: Euler trail No Euler cycle YesK4: Euler trail No Euler cycle NoK5: Euler trail No Euler cycle YesK6: Euler trail No Euler cycle No.K8: Euler trail No Euler cycle No9Class ExercisesA) Can a graph with an Euler cycle have a bridge (an edge whose removal disconnects the graph)?B) Give an example of a 10-edge graph with an Euler trail that has a bridge.Answers:No. If you start on one side of the bridge and then you cross it