Scribd
Upload
36 views1 page

Tutorial 3

The document outlines a series of graph theory problems and proofs, including paths, circuits, and Hamiltonian cycles. It discusses properties of graphs in relation to tournaments, friendship arrangements, and provides examples of connected graphs with specific characteristics. Additionally, it poses questions about Hamilton cycles in given graphs and the effects of removing vertices on Hamiltonian properties.

Uploaded by

Nandini Lokanath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
36 views1 page

Tutorial 3

The document outlines a series of graph theory problems and proofs, including paths, circuits, and Hamiltonian cycles. It discusses properties of graphs in relation to tournaments, friendship arrangements, and provides examples of connected graphs with specific characteristics. Additionally, it poses questions about Hamilton cycles in given graphs and the effects of removing vertices on Hamiltonian properties.

Uploaded by

Nandini Lokanath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Tutorial 3

1. Let a, b, and c be three distinct vertices in a graph. There is a path between a and b and also
there is a path between b and c. Prove that there is a path between a and c.
2. If the intersection of two paths is a disconnected graph, show that the union of the two
paths has at least one circuit.
3. A round-robin tournament (when every player plays against every other) among n players (n
being an even number) can be represented by a complete graph of n vertices. Discuss how
you would schedule the tournaments to finish in the shortest possible time.
4. Draw a graph that has a Hamiltonian path but does not have a Hamiltonian circuit.
5. Prove that a graph G with n vertices always has a Hamiltonian path if the sum of the degrees
of every pair of vertices vi, vj in G satisfies the condition d(vi) + d(vj) ≥ n − 1.
6. Using the result of Q6 show that in a dancing ring of n children it is always possible to
arrange the children so that everyone has a friend at each side if every child enjoys
friendship with at least half the children.
7. Provide an example of a connected graph that satisfies the following conditions:
(a) It has neither an Euler circuit nor a Hamiltonian cycle.
(b) It has an Euler circuit but does not have a Hamiltonian cycle.
(c) It has a Hamiltonian cycle but does not have an Euler circuit.
(d) It has both an Euler circuit and a Hamiltonian cycle.
8. Characterize the type of graph in which an Euler trail (circuit) is also a Hamilton path (cycle).
9. Find a Hamilton cycle, if one exists, for each of the graphs or multigraphs in Fig. 11.84. If the
graph has no Hamilton cycle, determine whether it has a Hamilton path.

10. Consider the graphs in parts (d) and (e) of Fig. 11.84. Is it possible to remove one vertex from
each of these graphs so that each of the resulting subgraphs has a Hamilton cycle?

You might also like