X3XAXY4Y3Y2YiK2K3.3onnectseithertwo(b)(a)in V2).The symbolVi=(x1,X2,X3,X4l, V=(yi.y2.y3.Y4.ys],or V'=(X1,X2,X3,Y4,ys), V'2=(yi,y2,3,x4)contains all edges joining vertices in VjK3,3, K2,30
❖5.2.4 Bipartite graph ❖ Definition18: A simple graph is called bipartite if its vertex set V can be partioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 . (so that no edge in G connects either two vertices in V1 or two vertices in V2 ).The symbol Km,n denotes a complete bipartite graph: V1 has m vertices and contains all edges joining vertices in V2 , and V2 has n vertices and contains all edges joining vertices in V1 . ❖ K3,3 , K2,3。 V1={x1 ,x2 ,x3, x4 }, V2={y1,y2,y3,y4,y5 }, or V'1={x1 ,x2 ,x3,y4,y5 }, V'2={y1,y2,y3, x4 }
VV2公多坊V3Um-1The graphis notbipartiteTheorem 5.5:A graph is bipartite iff it does notcontainany odd simplecircuit.Proof:(1)LetGbebipartite,we proveitdoesnot contain any odd simple circuit.Let C=(Vo,V1...,Vm,Vo) be an simple circuit of G
❖ The graph is not bipartite ❖ Theorem 5.5:A graph is bipartite iff it does not contain any odd simple circuit. ❖ Proof:(1)Let G be bipartite , we prove it does not contain any odd simple circuit. ❖ Let C=(v0 ,v1 ,.,vm,v0 ) be an simple circuit of G
(2)G does not contain any odd simplecircuit+we proveGis bipartiteSince a graph is bipartiteiff each componentof it is, we may assume that G is connected.Pick a vertex ueV,andput V,=xl(u,x)is evensimple path) ,and V2=yl(u,y) is odd simplepath)1)We prove V(G)=V, U V2, V,nV,-@Let veV,nV2,there is an odd simple circuit in G such thatthese edges of the simple circuit Cp, U p2each edgejoins avertexof V,toa vertex of V
❖ (2)G does not contain any odd simple circuit, we prove G is bipartite ❖ Since a graph is bipartite iff each component of it is, we may assume that G is connected. ❖ Pick a vertex uV,and put V1={x|l(u,x) is even simple path} ,and V2={y|l(u,y) is odd simple path} ❖ 1)We prove V(G)=V1∪V2 , V1∩V2 = ❖ Let vV1∩V2 , ❖ there is an odd simple circuit in G such that these edges of the simple circuit p1∪p2 ❖ each edge joins a vertex of V1 to a vertex of V2
2)we provethat eachedge of Gjoinsa vertex ofV, and a vertex VIfit has a edge joins two vertices yi and y2 of V,odd simple path(u=uo,uj,u2...,u2n,y1,y2),even pathy2*u;(0≤i<2n)There is u; so that y2=uj. The path (u,uj,u2,...,uj-1Y2,uj+1...,U2n,Yi,y2) from u to Y2,Simple path (u,u,u2...,uj-,y2),simple circuit(Y2,ui+19...,u2n9Yi,y2)jis odd numberjis even number
❖ 2) we prove that each edge of G joins a vertex of V1 and a vertex V2 ❖ If it has a edge joins two vertices y1 and y2 of V2 ❖ odd simple path ❖ (u=u0 ,u1 ,u2 ,,u2n,y1 ,y2 ),even path ❖ y2ui (0i2n) ❖ There is uj so that y2=uj . The path (u,u1 ,u2 ,,uj-1 , y2 ,uj+1,,u2n,y1 ,y2 ) from u to y2 , ❖ Simple path (u,u1 ,u2 ,,uj-1 ,y2 ),simple circuit (y2 ,uj+1,,u2n,y1 ,y2 ) ❖ j is odd number ❖ j is even number
5.3Euler and Hamilton paths5.3.1Eulerpaths+Definition 19:Apath in a graph Gis called anEuler path ifit includes every edge exactlyonce.An Euler circuit is an Euler path that isacircuitTheorem5.6:A connected multigraphhas anEuler circuitif and onlyif each of its verticeshasevendegree
5.3Euler and Hamilton paths ❖ 5.3.1 Euler paths ❖ Definition 19: A path in a graph G is called an Euler path if it includes every edge exactly once. An Euler circuit is an Euler path that is a circuit ❖ Theorem 5.6: A connected multigraph has an Euler circuit if and only if each of its vertices has even degree