Date:20 June 2018
Lemma1: A u-v walk, say W, contains a u-v path.
Proof:
(1)When the length of W, say l, is 0,certainly it includes a path of length 0 for it is an isolated vertex.
(2)Assume the proposition is true when lN. If l=N+1:
1. IfW has no repeated vertices, it is a path itself.
2. IfW has repeated ui, delete the edges and vertices between twoappearances of ui and let the resulting walk be W』. W』 is a walkwhose length is no greater than N, so based on our inductive hypothesis itcontains a path P. Also, because W』 is a subgraph of W, P is contained by W.Hence, W contains a path.
Proposition:A graph with n vertices and k edges has at least n-k components.
Proof:
Ann-vertex graph with no edges has n components. Adding 1 edge decrease thenumber of components by at most 1. Hence, a graph with n vertices and k edgeshas at least n-k components.
Theorem:An edge is a cut-edge if and only if it belongs to no cycle.
Proof:
Lemma2: A closed odd-walk, say W, contains a closed odd-cycle.
Proof:
(1) Ifthe length of the W, say l, is 1,then the closed odd-walk is a 1-cycle itself.
(2)Assume the proposition is true when lN. If l=N+1:
1. IfW has no repeated vertices, it is an odd-cycle itself.
2. IfW has a repeated vertex u, u divides the closed walk into two closed walk. Theparity of the lengths of the two closed walks must be different becauseotherwise W would be an even-walk. Hence, among the two closed walks there mustbe a closed odd-walk, say W』. The length of W』 is no greater than N, so W』contains an odd-cycle C. Also, because W』 is a subgraph of W, C is contained byW. W contains an odd-cycle.
Theorem:A graph is bipartite if and only if it contains no odd cycles.
Proof:
Necessity:
Let Gbe a bipartite graph. Every walk alternates between the two sets ofbipartition, so every return to the original bipartite set happens after aneven number of steps. Hence G has no odd cycle.
Sufficiency:
(1) Agraph is bipartite if and only if all of its components are bipartite. Hence,we assume G is connected.
(2)Select a vertex v of G at random. For any other vertex in G, say u, there existpaths from u to v, and if there are more than 1 path, the parity of the lengthsof those paths are all the same, otherwise a u-v path of odd length and a u-vpath of even length would form an odd closed-walk, which must contain anodd-cycle, together, as shown in Figure 1.
(3)Let E={u| uV(G), the lengths of all u-vpaths are even numbers}, O={u| uV(G), the lengths of all u-vpaths are odd numbers} (vE).
Certainly,if ui,ujE or ui,ujO, uiuj, uiand uj cannot be adjacent. Otherwise, and odd(even) ui-vpath, and odd(even) uj-v path and edge ui-ujwould form an odd closed-walk, which must contain an odd-cycle, as shown inFigure 2. It is okay if v is one of ui,uj. That’s becauseassume v= ui, without loss of generality, then uj mustbelong to E. Then an even uj-v path and edge uj-v wouldform an odd closed-walk, which contains an odd cycle, as shown in Figure 3.Hence, E and O is a bipartition of G. G is bipartite.
Theorem:A complete graph Kn is k-bipartite if and only if n2k.
Proof:
Whenk=1, because Kn contains odd cycle(s) when n3 but not when n3, Kn itself isbipartite if and only if n21. The propositionis true.
AssumeKn is bipartite only if n2k when kN. If k=N+1, suppose Kn=G1 G2Gk, where Giis bipartite. Divide V(Kn) into two parts X and Y such that Gkhas no edges within X or within Y. Certainly the union of the other k-1bipartite graphs G1,G2 must cover the two complete subgraphs of Knthat has vertex sets X and Y. Hence, |X|2k-1, |Y|2k-1, |Kn|=|X|+|Y|2k-1+2k-1=2k.
AssumeKn is bipartite if n2k when kN. If k=N+1 and n2k, divide the V(Kn)into two parts X and Y such that |X|, |Y|2k-1. Based on theinductive hypothesis, Kn’s complete subgraph on X, say K|X|,can be expressed as Gx1 Gx2Gxk-1, where GXiis bipartite, and Kn’s complete subgraph on Y, say K|Y|,can be expressed as GY1 GY2GYk-1, where GYiis bipartite. Since K|X| and K|Y| are two disjointsubgraphs of Kn, Gxi GYi is a bipartite graph. The unionof the k-1 bipartite graph, Gx1 GY1, Gx2 GY2,..., Gxk-1 GYk-1, already covers all edges ofKn except those of the biclique with bipartition X, Y. Let that bethe kth bipartite subgraph completes the construction.
Lemma3: If every vertex of G has degree at least 2, then G contains a cycle.
Proof:Let P be a maximal path in G, and let u be and endpoint of P. Since P cannot beextended, it must contain all neighbors of u. Also, because every vertex of Ghas degree at least 2, u has a neighbor v in V(P) via an edge not in P. Theedge uv completes a cycle with the portion of P from v to u.
Theorem:A graph is Eulerian if and only if it has at most 1 non-trivial component andall its vertices are even vertices.
Necessity: Suppose that G has Eulerian Circuit C. Each passage ofC through a vertex uses two incident edges, and the first edge paired with thelast at the first vertex. Hence all vertices have even degree. Also, two edgescan be in the same trial only if they lie in the same component, so there is atmost 1 non-trivial component.
Sufficiency:Let the two odd vertices of Gbe v1 andv2.Because G is connected, there must exist a v1-v2, path. Let this path be P. Take awaythe edges of P and get a new graph G』. The degree of v1 and v2 decrease by 1, and thedegree of all other vertexes decrease by 0 or 2. All the components of G』 areeither isolated vertices or connected graphs whose vertices all have evendegree no less than 2, having Eulerian cycle. Those components that areisolated vertices all belongs to P in G. They can be traversed easily. Forthose components that have Eulerian cycle and only have one common vertex Awith P, we only need to choose A as starting point and traverse them throughtheir Eulerian cycle, as shown in Figure 1. If a component of G』 with Euleriancycle have more than one common vertex, A1, A2, ..., An, with P, we can choose the Ai whosedistance from v1is the shortest as the starting point, and traverse it through itsEulerian cycle, as shown in Figure 2. By doing that, we can traverse all edgesof G without repeating any edges, so G has a Eulerian trail.
Proposition: If G is a simple graph in which every vertex hasdegree at least k, then G contains a path of length at least k. If k2,then G also contains a cycle of length at least k+1.
Proof: If u is an end-point of a maximal path of G, say P. Pcontains all neighbors of u because P cannot extend. Also, since u has degreeat least k, P has length at least k. If k2,G contains cycles. Assume u belongs to a maximal cycle contained by G, say C.Similarly, we can prove that C contains all neighbors of k and has length atleast k+1.
Proposition: Every even graph decomposes into cycles.
Proof: Assume G is an even graph. When |G|=3, G can only be atriangle. Certianly the proposition is true. Assume the proposition is truewhen |G|N.If |G|=N+1, based on lemma 3 we know that G contains a cycle, say C. BecauseG-C is also an even graph and |G-C|<N, based on our inductive hypothesis|G-C| decomposes into cycles. Hence, G=G-C+C decomposes into cycles.
Proposition: Every graph with a non-loop edge has at least twovertices that are not cut-vertices.
Proof:
If u is an end-point of the maximal path of the graph, say P.Since P cannot be extended, all neighbors of u are contained by P. Since P-u isconnected in G-u, all neighbors of u belong to a single component in G-u, whichmeans u is not a cut vertex.
Lemma: In an even graph, every maximal trail is closed.
Proof:
Let T be a maximal trail, v1-e1-v2-e2-...en-vn,in an even graph. Assume v is and end-point of T. if vnv1,despite e1, every passage of T through a vertex v uses two edges atv1, none repeated, so T uses an odd number of edges incident to v1in total. However, v has even degree. That means there remain an edge on whichT can continue, which is contrary to our assumption that T is a maximal trail.Hence, vn=v1 and T is closed.
After proving this, we can prove the sufficient and necessarycondition for being Eulerian in another way. Assume T is a maximal trail ineven graph G. We have proven that T is closed. Assume T omits a edge e of G.Since G is connected there is a shortest path from e to T, which means thereexists an edge e』 in G such that e』 incident to vV(T)but e』 is not contained by T. Adding e』 to T expand it into a longer trail,which is contrary to our assumption that T is maximal.
Theorem: For a connected nontrivial graph with exactly 2k oddvertices, the minimum number of trials that decompose it is max {k,1}.
Proof: A trail contributes even degree to every vertex, exceptthat a non-closed trail contributes odd degree to its endpoints. Therefore, apartition of the edge into trails must have some non-closed trail ending ateach odd vertex. Since each trail has only two ends, we must use at least ktrails to satisfy 2k odd vertices. We also need at least one trail since G hasan edge, and we have proven that one trail suffices when k=0.
It remains to prove that k trail suffice when k>0. Given such agraph G, we pair up the odd vertices in G and form G』 by adding for each pairan edge joining its two vertices. The resulting graph G』 is connected and even,which means it has an Eulerian circuit C. As we traverse C in G』, we start anew trail in G each time we traverse an edge of G』-E(G), this yields k trailsdecomposing G.