Chapter 10.5, Problem 65E

The parts of this exercise outline a proof of Ore's theorem. Suppose that G is a siraplegraph withnvertices, $n\ge 3$, and deg(x) + deg(y) $\ge$nwhenever x andyare non-adjacent vertices in G. Ore's theorem states that under these conditions, G has a Hamilton circuit.

a) Show that if G does not have a Hamilton circuit, then there exists another graph if with the same vertices as G, which can be constructed by adding edges to G, such that the addition of a single edge would produce a Hamilton circuit inH. [Hint:Add as many edges as possible at each successive vertex of G without producing a Hamilton circuit.]

b) Show that there is a Hamilton path in H.

e) Let v₁, v₂,...,v_nbe a Hamilton path in H. Show that deg(v₁) +deg(v_n) $\ge$nand that there are at most deg(v₁) vertices not adjacent tov_n(including v_nitself)..

JULIUS PETER CHRISTIAN' PETERSEN (1839-1910) Julius Petersen was born in the Danish town of Soro. His father was a dyer. In 1854 his parents were no longer able to pay for his schooling, so he became an apprentice in an uncle:s grocery store. When this uncle died, he left Petersen enough money to return to school. After graduating, he began studying engineering at the Poly technical School in Copenhagen, later deciding to concentrate on mathematics. He published his first textbook, a book on logarithms, in 1858. When his inheritance ran out, he had to teach to make a living. From 1859 until 1.871 Petersen taught at a prestigious private high school in Copenhagen. While teaching high school he continued his studies, entering Copenhagen University in 1862. He married Laura Eertelsen in 1862; they had three children, two sons and a daughter.

Petersen obtained a mathematics degree from Copenhagen University in 1866 and finally obtained his doctorate in 1871 from that school. After receiving his doctorate, he taught at a polytechnic and military academy. In 1887 he was appointed to a professorship at the University of Copenhagen. Petersen was well known in Denmark as the author of a large series of textbooks for high schools and universities. One of his books,MethodsandTheories for the Solution of Problems of Geometrical Construction,was translated into eight languages, with the English language version last reprinted in i960 and the French version reprinted as recently as 1990, more than a century after the original publication date.

Petersen worked in a wide range of areas, including algebra, analysis, cryptography, geometry, mechanics, mathematical economics, and number theory. His contributions to graph theory, including results on regular graphs, are his best-known work. He was noted for his clarity of exposition, problem-solving skills, originality, sense of humor, vigor, and teaching. One interesting fact about Petersen was that he preferred not to read the writings of other mathematicians. This led him often to rediscover results already proved by others, often with embarrassing consequences. However, he was often angry when other mathematicians did not read his writings!

Petersen's death was front-page news in Copenhagen. A newspaper of the time described him as the Hans Christian Andersen of science-a child of the people who made good in the academic world.

d)Let 5 be the set of vertices preceding each vertex adjacent to v₁in the Hamilton path. Show thatScontains deg(v₁) vertices andv_n??S.e) Show that 5 contains a vertex v_kthat is adjacent to v_n, implying that there are edges connecting v₁and v_k+1and v_kandv_n.