1936; Chelsea, New York, 1950.
1-8. LIETZMANN, W., Visual Topology, American Elsevier Publishing
Company, Inc., New York, 1965. English translation of the German book
Anschauliche Topologie, R. Oldenbourg K. G., Munich, 1955.
1-9. ORE, O., Theory of Graphs, American Mathematical Society,
Providence, R.I., 1962.
1-10. ORE, O., Graphs and Their Uses, Random House, Inc., New York, 1963.
1-11. ORE, O., The Four Color Problem, Academic Press, Inc., New York,
1967.
1-12. ROUSE BALL, W., Mathematical Recreations and Essays, London and
New York, 1892; and The Macmillan Company, New York, 1962.
1-13. SESHU, S., and M. B. REED, Linear Graphs and Electrical Networks,
Addison-Wesley Publishing Company, Inc., Reading, Mass., 1961.
PROBLEMS
1-1. Draw all simple graphs of one, two, three, and four vertices.
1-2. Draw graphs representing problems of (a) two houses and three utilities;
(b) four houses and four utilities, say, water, gas, electricity, and
telephone.
1-3. Name 10 situations (games, activities, real-life problems, etc.) that can
be represented by means of graphs. Explain what the vertices and the
edges denote.
1-4. Draw the graph of the Wheatstone bridge circuit.
1-5. Draw graphs of the following chemical compounds: (a) CH4, (b) C2H6,
(c) C6H6, (d) N2O3. (Hint: Represent atoms by vertices and chemical
bonds between them by edges.)
1-6. Draw a graph with 64 vertices representing the squares of a chessboard.
Join these vertices appropriately by edges, each representing a move of
the knight. You will see that in this graph every vertex is of degree two,
three, four, six, or eight. How many vertices are of each type?
1-7. Given a maze as shown in Fig. 1-13, represent this maze by means of a
graph such that a vertex denotes either a corridor or a dead end (as
numbered). An edge represents a possible path between two vertices.
(This is one of numerous mazes that were drawn or built by the Hindus,
Greeks, Romans, Vikings, Arabs, etc.)
www.TechnicalBooksPDF.com
Fig. 1-13 A maze.
1-8. Decanting problem. You are given three vessels A, B, and C of capacities
8, 5, and 3 gallons, respectively. A is filled, while B and C are empty.
Divide the liquid in A into two equal quantities. [Hint: Let a, b, and c be
the amounts of liquid in A, B, and C, respectively. We have a + b + c = 8
at all times. Since at least one of the vessels is always empty or full, at
least one of the following equations must always be satisfied: a = 0, a =
8; b = 0, b = 5; c = 0, c = 3. You will find that with these constraints there
are 16 possible states (situations) in this process. Represent this problem
by means of a 16-vertex graph. Each vertex stands for a state and each
edge for a permissible change of states between its two end vertices.
Now when you look at this graph it will be clear to you how to go from
state (8, 0, 0) to state (4, 4, 0).] This is the classical decanting problem.
1-9. Convince yourself that an infinite graph with a finite number of edges
(i.e., a graph with a finite number of edges and an infinite number of
vertices) must have an infinite number of isolated vertices.
1-10. Show that an infinite graph with a finite number of vertices (i.e., a graph
with a finite number of vertices and an infinite number of edges) will
have at least one pair of vertices (or one vertex in case of parallel self-
www.TechnicalBooksPDF.com
loops) joined by an infinite number of parallel edges.
1-11. Convince yourself that the maximum degree of any vertex in a simple
graph with n vertices is n – 1.
1-12. Show that the maximum number of edges in a simple graph with n
vertices is n(n – l)/2.
†The adjective “linear” is dropped as redundant in our discussions, because by a graph we always mean a
linear graph. There is no such thing as a nonlinear graph
†Some authors (see, for example, [2-9], p. 1, or [15-58], p. 17) do allow the case in which the vertex set V is
also empty. This they call the null graph, and they call a graph with E = Ø and V ≠ Ø a vertex graph. For
our purposes this distinction is of no consequence. For a lively discussion on paradoxes arising out of
different definitions of the null graph, see pp. 40-41 in Theory of Graphs: a Basis for Network Theory, by L.
M. Maxwell and M. B. Reed (Pergamon Press, N. Y. 1971).
† Bracketed numbers refer to references at the end of chapters.
www.TechnicalBooksPDF.com
