Eulerian and Hamiltonian Graphs

Question 1

eulerian trail:

Answer 1

a trail in a multigraph that includes each edge exactly once

Question 2

eulerian tour:

Answer 2

a eulerian trail that starts and ends at the same vertex

Question 3

eulerian multigraph:

Answer 3

a multigraph that contains a eulerian tour

Question 4

prove that the following statements for a connected multigraph G are equivalent - (1) G is eulerian, (2) each vertex of G has even degree, and (3) the edge set of G can be partitioned into cycles:

Answer 4

just gotta prove (1)->(2), (2)->(3), and (3)->(1)
(1)->(2) - G is eulerian, so we know it contains a trail that includes each edge exactly once - label the vertices so we have v0,…,vm (vm=v0 cause closed) where |E|=m - the same vertex can be repeated in this sequence. G is connected so every vertex is included. take some vertex vj, 0<j<m, gotta appear at least once and in a pair of successive edges every time (v(j-1),vj), (vj,v(j+1)), so deg(vj) is a sum of 2s, so it’s even. v0 appears at the start and the end so same deal
(2)->(3) - this actually works for unconnected graphs also
base case - a multigraph with |E|=0, so partitioned into 0 cycles success
hypothesis - this applies to all multigraphs with only vertices of even degree and |E|<=m0, can partition all into disjoint cycles
induction - if a graph has only even degrees and |E|>0, there must be a cycle (separate lemma dw about it for now) - G has |E|=m0+1, G’(V,E’)=G\that cycle, all degrees are still even cause all degrees in a lone cycle are and all the rest have been decreased by 2, the G’ has 1<|E’|<=m0 cause the cycle has at least 1 edge, so the hypothesis applies to G’, and then just add the cycle to the partition for the partition of G
(3)->(1) - this is trivial unless the partition of E involves at least 2 cycles so that’s what we’re proving. we can always merge 2 cycles into a longer trail by using the common vertex (there can be no common edges, but if it’s connected, there must be a common vertex), so voila

Question 5

hamiltonian path:

Answer 5

a path that includes all vertices exactly once

Question 6

hamiltonian tour:

Answer 6

/cycle, a cycle that includes every vertex

Question 7

hamiltonian graph:

Answer 7

a graph that contains a hamiltonian cycle
means |V|>=3 for all, to be able to have a cycle

Question 8

hamiltonian graph examples:

Answer 8

the cycle graphs, obviously, and the complete graphs

Question 9

closure:

Answer 9

[G], constructed by adding edges that connect pairs of non-adjacent vertices for which deg(u)+deg(v)>=n where n=|V|
continues until all non-adjacent pairs satisfy deg(u)+deg(v)<n
do this sequentially, testing all possible edges from v1 and so on - either it already exists, you can add it, or you can’t add it, then repeat for the new graph until you can’t add any

Question 10

bondy-chvatal theorem and proof:

Answer 10

theorem - (1) a graph is hamiltonian iff (2) its closure is hamiltonian
(1)->(2) is easy, adding edges won’t do shit, the graph will still be hamiltonian with the same series of vertices and edges
(2)->(1) - assume for a contradiction that G isn’t hamiltonian but [G] is. if Gi is hamiltonian, so are all Gj (j>i). think about the closure process, there then must be some Gi such that Gi isn’t hamiltonian, but Gj is. but these graphs would only differ in one edge, which is impossible