Chapter 3 Flashcards
Defn/ An Eulerian circuit is:
A Eulerian circuit is a circuit (repeated edges, no repeat vertices) in a multigraph containing all edges.
Defn/ A graph is Eulerian if:
it has an Eulerian circuit
Lemma: A multigraph G contains a circuit if every vertex is even, some with positive degree.
Pick vertex v with degree >0, and form a travel T by randomly choosing edges not previously traversed. Suppose this stops at vertex w. If v=w, done. If v!=w, that means number of edges in T incident to w is odd (there must be another way out if they were even) thus contradiction.
Thm: A multigraph G is Eulerian IFF the vertices of G are even and connected.
Pf (Eulerian => Even degree).
Let C be Uelerian cicuit. For each v in G, there are even num edges in C incident. since C Eulerian, vertex degree is equal to the # of incident edges in C.
(Even deg => Eulerian)
Apply lemma, G has a circuit C. If C is not Eurlerian, there exists a vertex u in C, incident to edges not in C. Construct a multigraph H by removing edges in C. H also has vertices of even degree, so by lemma, there exists a curcuit C’ containing u in H. Then create a new circuit by concatenating C, C’. Repeat until all edges are accounted for.
Corr: A multigraph is Eulerian IFF its edge set can be partitioned into cycles
no proof
Def/ A multigraph G is traversible if:
Traversible if G has a trail T which has all edges of G, AKA has a Eulerian trail.
Thm: G is traversible IFF all but 2 vertices of G are even, and G is connected.
Let v1, v2 be vert of odd degree. Then, G+v1v2 is Eulerian (could be 2 edges between the verts).
G + v1v2 has Eulerian circuit C
G + v1v2 is an Eulerian trail in G.
Def/ A graph G is Hamiltonian if:
there is a cycle (no repeated edges or vert) in G containing all vertices
Thm: If G has order p>= 3 (123 all trivial), min degv >=p/2, then G is Hamiltonian.
Pf: Step 1: Let path P = u1,u2,u3,…, u.k by a maximal path. Since degu1 >= p/2, |P|>= 1 + p/2.
Step 2: Claim there exists a vertex u.2, 2<=i<=k so u.1 adjacent to u.i and u.k adjacent to u.i-1. BWOC, suppose for each u.1 adjacent to u.1, u.i-1 is NOT adjacent to u.k.
There are at least p/2 vertices adjacent to u.k
Lemma: If u,v non-adj. and degu + degv >= p, then if G+uv Ham. => G also Ham.
Same idea as the “If G has order p>=4, and min degv >= p/2, then G is Hamiltonian” proof with proving the vertex path setup exists due to how many vertices are connected.
Def/ the closure of G is:
the closure of G is obtained by recursively joining pairs of nonadj. vert. uv where degu + degv >=p
Thm: A graph is Ham IFF it’s closure is Ham.
First way follows from lemma that G + uv, where u,v degrees summed are >=p implies that G also Ham, and second way is simply because adding edges does not affect if something is Ham.
