Page 727 - Discrete Mathematics and Its Applications

706 10 / Graphs

∗ 46. Show that the Petersen graph, shown here, does not have 48. Can you find a simple graph with n vertices with n ≥ 3
a Hamilton circuit, but that the subgraph obtained by that does not have a Hamilton circuit, yet the degree of
deleting a vertex v, and all edges incident with v, does every vertex in the graph is at least (n − 1)/2?
have a Hamilton circuit.
∗ 49. Show that there is a Gray code of order n whenever n is
a a positive integer, or equivalently, show that the n-cube
Q n ,n > 1, always has a Hamilton circuit. [Hint: Use
mathematical induction. Show how to produce a Gray
f
code of order n from one of order n − 1.]
e b
Fleury’s algorithm, published in 1883, constructs Euler cir-
j g
cuits by first choosing an arbitrary vertex of a connected multi-
graph, and then forming a circuit by choosing edges succes-
i h
sively. Once an edge is chosen, it is removed. Edges are cho-
sen successively so that each edge begins where the last edge
d c ends, and so that this edge is not a cut edge unless there is no
alternative.
47. For each of these graphs, determine (i) whether Dirac’s
theorem can be used toshowthatthegraph hasaHamilton 50. Use Fleury’s algorithm to find an Euler circuit in the graph
circuit, (ii) whether Ore’s theorem can be used to show G in Figure 5.
that the graph has a Hamilton circuit, and (iii) whether
∗ 51. Express Fleury’s algorithm in pseudocode.
the graph has a Hamilton circuit.
∗∗ 52. Prove that Fleury’s algorithm always produces an Euler
a) b)
circuit.
∗ 53. Give a variant of Fleury’s algorithm to produce Euler
paths.
54. A diagnostic message can be sent out over a computer
network to perform tests over all links and in all devices.
c) d) What sort of paths should be used to test all links? To test
all devices?
55. Show that a bipartitegraph withan oddnumberofvertices
does not have a Hamilton circuit.

JULIUS PETER CHRISTIAN PETERSEN (1839–1910) Julius Petersen was born in the Danish town of
Sorø. 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 Polytechnical 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 1871 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 Bertelsen 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, Methods and Theories for the Solution of Problems of Geometrical
Construction, was translated into eight languages, with the English language version last reprinted in 1960 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.