Donna Kirk

Your Turn

12.1

1.

On a graph the objects are represented with dots and their connects are represented with lines. The dots are the vertices. The vertices are p, q, r, s, and t. The line segments joining the vertices are called edges. The edges are pq, pr, pt, qr, qs, qt, rs, and st.

The vertices are p, q, r, s, and t. The edges are pq, pr, pt, qr, qs, qt, rs, and st.

12.2

1.

Adjacent vertices share a common edge. Vertices that are not adjacent do not share a common edge. Vertices p and s do not share a common edge, and so are not adjacent. Likewise, vertices r and t do not share a common edge and thus are not adjacent.

The pairs that are not adjacent are p and s, and r and t.

12.3

1.

The degree of a vertex is the number of edges that connect to that vertex. Vertex q has four edges that connect to it. Think of standing at a street corner and counting how many streets lead away from your corner.

Vertex q

12.4

1.

Draw a vertex to represent each region. Label each with the initial of the region (N for North Shore, L for Leeward Coast, C for Central, S for South, and W for Windward Coast). Draw edges to connect vertices that share a common border. The North Shore region shares a border with Leeward Coast, Central, and Windward Coast, so draw an edge from N to L, C, and W.

Leeward Coast shares a border with North Shore and Central. You already have the edge between N and L, so all you need to add is the edge between N and C.

Central shares a border with all the other four regions. You need to add an edge to W and S.

Windward shares a border with North Shore, Central, and South. You already have the edge to N and C, so add the edge to S.

South shares a border with Central and Windward. You already have both of those. You are done.

Go back over your drawing and the map. Count the degree of your vertices and compare it to the “degree” of each region on the map.

A graph represents common boundaries between regions of Oahu. The five vertices are L, N, W, C, and S. Edges connect L with N and C. Edges connect N with W and C. Edges connect W with C and S. An edge connects S with C.

Graph Representing Common Boundaries Between Regions of Oahu

12.5

1.

The objects that are represented with vertices are poker players. An edge between a pair of vertices would indicate the two players competed against each other at table. This is best represented as a graph because players from the same table never meet a second time. Also, a player cannot compete against themself; so, there is no need for a loop.

12.6

1.

Scientists consider communities with more connections more resistant to failure because they have more options. A graph of such a community will have a higher sum of its degrees.

Degree	Graph
Vertex	C	D	E
a	3	3	5
b	3	1	3
c	2	1	5
d	3	1	1
e	3	4	5
f	2	2	4
g	2	2	4
h	2	1	4
i	3	3	3
Sum	23	18	34

The graph with the highest degree is graph E. The sum of the degree of its vertices is 34.

Graph E, 34

2.

Scientists consider communities with more connections more resistant to failure because they have more options. A graph of such a community will have a higher sum of its degrees.

Degree	Graph
Vertex	C	D	E
a	3	3	5
b	3	1	3
c	2	1	5
d	3	1	1
e	3	4	5
f	2	2	4
g	2	2	4
h	2	1	4
i	3	3	3
Sum	23	18	34

The graph with the least degree is graph D. The sum of the degree of its vertices is 18.

Graph D, 18

3.

Scientists consider communities with more connections more resistant to failure because they have more options. A graph of such a community will have a higher sum of its degrees.

higher

12.7

1.

The number of edges is half the number of the sum of degrees. If the sum of degrees is 6, then there are 3 edges.

3

2.

Possible graphs with 3 edges and a sum of 6 degrees.
One graph labeled graph 1. The graph has four vertices labeled 1, 2, 2, and 1. The edges connect 1 2, 2 2, and 2 1.

One graph labeled graph 1. The graph has four vertices labeled 1, 2, 2, and 1. The edges connect 1 2, 2 2, and 2 1.

or

One graph labeled graph 2. The graph has four vertices labeled 1, 3, 1, and 1. The edges connect 1 3, 3 1, and 3 1.

Answers may vary. Two possible graphs are shown.
Graph 1:
One graph labeled graph 1. The graph has four vertices labeled 1, 2, 2, and 1. The edges connect 1 2, 2 2, and 2 1.

Graph 2:

12.8

1.

There are 500 vertices. Each individual must meet 499 other strangers, so there are 499 edges meeting at each vertex. Since there are 500 vertices of degree 499, the sum of degrees is 500(499) = 249,500.

By the Sum of Degrees Theorem, ${\text{the number of edges = }}\frac{{{\text{sum of degrees}}}}{2} = \frac{{249,500}}{2} = 124,750{\text{ introductions}}$ .

124,750 introductions

12.9

1.

Graph F has four vertices: V, W, X, and Z. The edges connect X W, X V, V W, X Z, and W Z.

12.10

1.

A cycle is a series of connected edges that begins and ends at the same vertex but otherwise never repeats any vertex. When cycles appear as subgraphs within a larger graph, they are called cyclic subgraphs and are named by listing their vertices sequentially. It helps you keep track by naming them by starting with the letter that comes earliest in the alphabet. They are named based on the number of edges they have. A triangle has three sides. A quadrilateral has four sides. A pentagon has five sides.

Triangle: (a, b, e)	Alternate answer option for Triangle: (a, d, e)
Quadrilateral (a, b, e, d)	Alternate answer option for Quadrilateral: (b, c, d, e)
Pentagon (a, b, c, d, e)

Triangle: (a, b, e or a, d, e)
Quadrilateral: (b, c, d, e or a, b, e, d)
Pentagon: (a, b, c, d, e)

12.11

1.

A cycle is a series of connected edges that begin and end at the same vertex but otherwise never repeats any vertex. When cycles appear as subgraphs within a larger graph, they are called cyclic subgraphs and are named by listing their vertices sequentially. It helps you keep track by naming them by starting with the letter that comes earliest in the alphabet. They are named based on the number of edges they have.

A pentagon has five sides. If the vertices are named by the person’s initial, then there is a pentagon cycle (B, D, C, E, F).

Alternate answer option: You could also have gone around the cycle in the other direction.

(B, F, E, C, D). Your answers are more likely to match the solutions if you choose the next vertex that comes first in alphabetical order.

(B, D, C, E, F)

12.12

1.

You need Entry 3 in Row 13, but there is no Row 13 in the Pascal triangle provided. You need to make one. You do not need to make the whole row. The entries in the new row are the sum of the entries sitting on its “shoulders.”

Row 10				1		10		45		120		210		…
Row 11			1		11		55		165		330		…
Row 12		1		12		66		220		495		…
Row 13	1		13		78		286		781		…
ENTRY	0		1		2		3

Entry 3 in Row 13 is 286.

286

12.13

1.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.
There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

Graph C₁ has 6 edges, but Graph C₂ has 8.

Graph C₁ has 4 vertices, and Graph C₂ has 5.

Graph C₁ has no vertex of degree 4, but Graph C₂ has one vertex of degree 4.

They do not have the same cycles. For example, Graph C₂ has a pentagon cycle, but Graph C₁ does not.

Graph C₁ has 6 edges, but Graph C₂ has 8.
Graph C₁ has 4 vertices and Graph C₂ has 5.
Graph C₁ has no vertex of degree 4, but Graph C₂ has one vertex of degree 4.
They do not have the same cycles. For example, Graph C₂ has a pentagon cycle, but Graph C₁ does not.

12.14

1.

Answers may vary.

The total number of vertices in each graph is different. The Diamonds graph has 17 vertices while Dots graph has only 16.
The degrees of vertices differ. The Diamonds graph has vertices of degrees 4 while the Dots graph does not.
The graphs have different sizes of cyclic subgraphs. The Diamonds graph has 4 squares (4-cycles), while the Dots graph has 3 squares. Also, the Dots graph has 8-cycles while the Diamonds graph does not.

12.15

1.

Answers may vary. There are four possible isomorphisms:

a − q, d − s, c − p, and b − r.
a − p, d − s, c − q, and b − r.
a − q, d − r, c − p, and b − s.
a − p, d − r, c − q, and b − s.

12.16

1.

Be careful you do not do what Javier did. Javier highlighted a crossover where there is no vertex. There is no cyclic subgraph in graph E.

Maubi is incorrect because you can trace your finger around Graph E from vertex a back to a. Graph E is a quadrilateral, a four-sided cycle (a, b, c, d). Graph T also is a four-sided cycle (p, q, r, s).

Both graphs have 4 vertices, 4 edges, and no cyclic subgraphs. All the vertices have degree 2.

By flipping vertex d around c, you can transform Graph E into visual facsimile of Graph T.

Caden is correct because Graph E could be untangled so that d is to the left of c and the edges bc and ad are no longer crossed. Maubi is incorrect because (a, b, c, d) is a quadrilateral in Graph E. Javier is incorrect because the portion of the graph he highlighted does not have 3 vertices and is not a triangle.

12.17

1.

One way to find the complement of a graph is to draw the complete graph with the same number of vertices and remove all the edges that were in the original graph.

Vertex A has a degree of 0.

The other vertices will be connected in a line, C to E to B to D. Each will have a degree of 2.

The edges are BD, CE, EB.

The complement of graph H is displayed. The vertices are A, B, C, D, and E. The edges connect B E, B D, and E C.

12.18

1.

You know the degrees will be 0.

One way to find the complement of a graph is to draw the complete graph with the same number of vertices and remove all the edges that were in the original graph. Since the original graph is a complete graph, the complement will have no edges.

The degrees are 0. There are no adjacent vertices in Graph N since all vertices are adjacent in Graph M.

12.19

1.

b

a) If you follow B to V, you are in Brooklyn and end up at a dead end.

b) This walk takes you through all the bridges exactly once.

c) When you follow C to V, you are in Brooklyn and end up at a dead end.

d) When you follow G to V, you are in Brooklyn and end up at a dead end.

Only V → C → B → G → C is a walk.

12.20

1.

To make sure it is a walk, check to see if the vertices are consecutive.

The vertices are consecutive, so it is a walk.

A trail has no repeated edges.

A path has no repeated vertices.

Since there are no repeated edges or vertices, this is a walk, path, and a trail.

walk, path, and trail

2.

To make sure it is a walk, check to see if the vertices are consecutive.

The vertices are consecutive, so it is a walk.

A trail has no repeated edges. Draw the graph on paper. Then trace the path with another color. You will see that you have no repeated edges. This is a trail.

A path has no repeated vertices. The vertex n is used twice, so this is not a path. This is a walk and a trail, but not a path.

walk and a trail, but not a path

3.

The last two vertices, p and q, are not adjacent. All the vertices in a walk must be adjacent. This is not a walk. If it is not a walk, it can be neither a trail nor a path.

none of these

12.21

1.

Walks that visit the same edge twice are not circuits. To fly from Palm Beach to any other city, you must take the flight from PBI to TPA. To return, you must take the flight from TPA to PBI. This means that the graph of any itinerary that begins and ends at PBI covers the same edge twice and is not a circuit.

To fly from Palm Beach to any other city, you must take the flight from PBI to TPA. To return, you must take the flight from TPA to PBI. This means that the graph of any itinerary that begins and ends at PBI covers the same edge twice and is not a circuit.

2.

Walks that visit the same edge twice are not circuits. To start at PBI and return to PBI, you must use the edge from TPA to PBI twice. The degree of PBI is 2. A circuit will start and end on vertices with degree 1 and have vertices with degree 2 along the way as it passes through vertices. It cannot start at a vertex with degree 2 as happens in this trip.

The degree of PBI is 1 meaning that there is only one edge connecting PBI to other parts of the graph.

12.22

1.

Yes, the graph is planar. A planar graph can be drawn on a flat surface so that no two edges are crossing. This graph has no edges crossing. The chromatic number of a planar graph is four or less.

Yes. The chromatic number is 4 or less.

2.

The graph has triangular cliques. The chromatic number of a graph is at least the number of vertices in its biggest cliques. Thus, the chromatic number of this graph is at least 3.

3

3.

Because it is planar, the chromatic number is 4 or less. Because the largest clique is a triangle, the chromatic number is at least 3. Putting this information together, the chromatic number is either 3 or 4.

3 or 4

4.

Graphs 1 and 3 are valid. Graph 2 is not since it has two adjacent vertices with the same color. Graph 3 is valid even though it uses more colors than it needs to use.

Graphs 1 and 3

5.

Answers may vary. Here is an example of a 3-coloring:

A graph with seven vertices. It has 2 vertices in red, 3 vertices in blue, and 2 vertices in purple. Edges from the first red vertex lead to two blue vertices and two purple vertices. The first purple and the first blue vertices are connected by an edge. The second purple and the second blue vertices are connected by an edge. The second purple connects with the second red and third blue via edges. The second red and third blue are connected via an edge.

12.23

1.

Because it is planar, the chromatic number is 4 or less. Because the largest clique is a triangle, the chromatic number is at least 3. Putting this information together, the chromatic number is either 3 or 4. It can be done with 3 colors, so its chromatic number is 3.

The chromatic number is 3. Here is a 3-coloring of the graph:
A graph represents common boundaries between regions of Oahu. The five vertices are L, N, W, C, and S. L and W are in purple. N and S are in blue. C is in red. Edges from L connect with N and C. Edges from N connect with W and C. Edges from W connect with C and S. An edge from S connects with S.

A graph represents common boundaries between regions of Oahu. The five vertices are L, N, W, C, and S. L and W are in purple. N and S are in blue. C is in red. Edges from L connect with N and C. Edges from N connect with W and C. Edges from W connect with C and S. An edge from S connects with S.

12.24

1.

A graph is connected if it has only one component. Graphs G, H, and I are connected; so, they each have a single component with the vertices {a, b, c, d}.

A graph is disconnected if it has more than one component. Graph F is disconnected with two components: {a, c, d} and {b}. Graph J is disconnected with two components: {a, d} and {b, c}. Graph K is disconnected with three components: {a}, {b, d}, and {c}.

Graphs G, H, and I are connected; so, they each have a single component with the vertices {a, b, c, d}. Graph F is disconnected with two components, {a, c, d} and {b}. Graph J is disconnected with two components, {a, d} and {b, c}. Graph K is disconnected with three components, {a}, {b, d}, and {c}.

12.25

1.

A graph is connected if there is a path joining every pair of vertices on the graph. Each pair of vertices would be connected by a path that was at most six edges long. So, the graph would be connected.

Each pair of vertices would be connected by a path that was at most 6 edges long. So, the graph would be connected.

12.26

1.

The multigraph of the neighborhood is shown:
A graph of a neighborhood has 16 vertices arranged in 4 rows and 4 columns. The vertices are connected to form 9 squares. On each side, a curved edge connects the center two vertices.

A graph of a neighborhood has 16 vertices arranged in 4 rows and 4 columns. The vertices are connected to form 9 squares. On each side, a curved edge connects the center two vertices.

2.

A component of a graph is a subgraph in which there is a path between each pair of vertices in the subgraph, but no edges between any of the vertices in the subgraph and a vertex that is not in the subgraph. A graph is connected if it has only one component. You also know it is connected because there is a path joining every pair of vertices on the graph.

Yes, the graph is connected. It has only one component.

3.

There are four corner vertices of degree 2 and the remaining twelve vertices are all degree 4.

4.

Eulerian graphs have vertices with all even degrees. All the vertices in this graph are either degree 2 or degree 4, so this is Eulerian.

Yes

5.

Yes, an Eulerian graph has an Euler circuit; so, it is possible.

12.27

1.

In an Euler circuit, you can start at a vertex, visit all the other vertices exactly once, and return to the original circuit. This is impossible in Graph X because it is disconnected.

Graph X does not have an Euler circuit because it is disconnected.

2.

In an Euler circuit, you can start at a vertex, visit all the other vertices exactly once, and return to the original circuit. The Euler circuit in Graph Y is a → b → g → d → f → c → g → e → a.

a → b → g → d → f → c → g → e → a

12.28

1.

You want to add the fewest possible edges, and you can only duplicate existing edges. The most efficient way to eulerize the graph is to duplicate a-d.

Graph Z has four vertices: a, b, c, and d. The edges connect a b, b d, d c, and c a. A double edge connects a to d.

12.29

1.

Draw the graph lightly. Then draw the sequence of edges in another color. Since you have covered all the edges exactly once, this is an Euler circuit.

Yes.

2.

Draw the graph lightly. Then draw the sequence of edges in another color. Since you have not covered all the edges exactly once, this is not an Euler circuit. You missed cd and de.

No. It doesn’t cover every edge.

3.

Draw the graph lightly. Then draw the sequence of edges in another color. Since you have not covered all the edges exactly once, this is not an Euler circuit. In this case, it is not even possible to follow the sequences since b and e are not adjacent.

No. It is not a walk, because the vertices b and e are not adjacent.

12.30

1.

In a complete graph with three or more vertices, any three vertices form a triangle which is a cycle. Any edge in a graph that is part of a cycle cannot be a bridge so, there are no bridges in a complete graph. Also, any edge that is part of a triangle cannot be a local bridge because the removal of any edge of a triangle will leave a path of only two edges between the vertices of that edge. So, there are no bridges or local bridges in a complete graph.

12.31

1.

Step 1: If there are two odd vertices, begin at one odd vertex and end at the other.

There are two odd vertices, m and s. Fill the blank with m.

m

2.

Step 1: If there are two odd vertices, begin at one and end at the other.

You began at s.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

You removed sq. You are now at vertex q. The edges that leave from this vertex are qr, qt, and qn. Fill in the first two blanks with qn and qt (in any order). You cannot choose qn because it is a bridge. Write “qn” in the third blank. Write “bridge” in the last blank.

qn, qt; qn bridge

3.

Step 1: If there are two odd vertices, begin at one and end at the other.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

You are still working on the right half of the figure. You need to remove the remaining edges in the right half. Draw the figure and color the edges as you remove them to help you keep track of what you have removed.

So far, you have removed sq and qr.

Now you can go around the right half of the graph. Remember, do everything possible before you cross a bridge.

sq, qr, rs, st, tq

Now you are ready to cross the bridge.

nq

rs, st, tq, qn

4.

Step 1: If there are two odd vertices, begin at one and end at the other.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

Now you have polished off the right half of the figure. You need to remove the remaining edges in the left half. Draw the figure and color the edges as you remove them to help you keep track of what you have removed.

What you have already done: sq, qr, rs, st, tq, nq

You are at vertex n.

You have three options now: no, nm, or np.

nm, np

5.

Step 1: If there are two odd vertices, begin at one and end at the other.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

Now you have polished off the right half of the figure. You need to remove the remaining edges in the left half. Draw the figure and color the edges as you remove them to help you keep track of what you have removed.

What you have already done: sq, qr, rs, st, tq, nq, no

The only edge away from o that you have used is om.

From this point, you can go around the triangle to n and p in either direction to come back to m.

om, mp, pn, nm.

Alternate answer option:

om, mn, np, pm

om, mp, pn, nm

6.

Step 1: If there are two odd vertices, begin at one and end at the other.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

Now you have polished off the right half of the figure. You need to remove the remaining edges in the left half. Draw the figure and color the edges as you remove them to help you keep track of what you have removed.

What you have already done: sq, qr, rs, st, tq, nq, no

The only edge away from o that you have used is om.

From this point, you can go around the triangle to n and p in either direction to come back to m.

om, mp, pn, nm.

Alternate answer option:

om, mn, np, pm

Step 3: Write out the Euler trail using the sequence of vertices and edges you found.

s → q → r → s → t → q → n → o → m → p → n → m

Alternate answer options are possible.

s → q → r → s → t → q → n → o → m → p → n → m

12.32

1.

Step 1: If there are two odd vertices, begin at one odd vertex and end at the other.

Vertices u and v are odd, so you must begin at one and end at the other. It doesn’t matter which you choose as the beginning as which you choose as the end.

Step 2: Remove an edge between the vertex and any adjacent vertex that is not a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all the edges are removed.

Step 3: Write out the Euler trail using the sequence of vertices and edges you found.

v → w → x → u → z → y → w → u

Other variations are possible.

The graph has Euler trails. They must begin and end at vertices u and v. An example is
v → w → x → u → z → y → w → u

12.33

1.

Euler circuits visit every edge exactly once. Hamilton cycles visit every vertex exactly once. This circuit does both, so it is both an Euler circuit and a Hamilton cycle.

both

12.34

1.

n! = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720

and

\left( {n - 1} \right)! = (6 - 1)! = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120

12.35

1.

The number of ways to arrange n distinct objects is n!.

There are 5 letters, so there are 5! ways to arrange them.

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120

12.36

1.

The number of distinct Hamilton cycles in a complete graph with n vertices is (n – 1)!.

This graph has six vertices, so it has (6 – 1)! distinct Hamilton cycles.

$\left( {6 - 1} \right)! = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

120

12.37

1.

Add the weights of the individual edges.

mo	op	pn	nq	qm	Sum
3	5	5	8	5	26

The total weight of the Hamilton cycle is 26.

26

12.38

1.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. It does not need to start and end on the same vertex.

This sequence is impossible since c and d are not adjacent.

No

2.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. It does not need to start and end on the same vertex.

This sequence is not a Hamilton path since vertex b is visited in the midst of the path, as well as being the start and ending vertex.

No

3.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. It does not need to start and end on the same vertex.

This sequence is a Hamilton path.

Yes

12.39

1.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. It does not need to start and end on the same vertex.

Since you start at C, A must be next. So far you have:

C → A

If you then went to F, you would have no way to get to B without visiting F twice. So, you must go from A to B. Then from B to F.

C → A → B → F

You need to end at E, so visit D next.

C → A → B → F → D

Finally, end at E.

C → A → B → F → D → E

C → A → B → F → D → E

12.40

1.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. It does not need to start and end on the same vertex.

To find a bridge, avoid the bridges until you must cross them. This graph has a bridge (nq), so stay as far away from it as you can.

Since you start at p, avoid being near the bridge and choose m. So far you have:

p → m

Since you are staying away from the bridge, go to o.

p → m → o

Time to go over the bridge.

p → m → o → n → q

You need to end at r, so go around the vertices to end at r.

p → m → o → n → q → t → s → r

p → m → o → n → q → t → s → r

2.
You cannot find a Hamilton path that starts at m and ends at p since they are on the same side of bridge nq.
none

3.
You cannot find a Hamilton path that starts at o and ends at q since this sequence ends at one end of the bridge nq. The Hamilton path would have to go around the four-cycle subgraph on the left, cross the bridge (nq), and then go round the four-cycle subgraph on the right. Hamilton paths cannot start or end on the vertices that form the bridge. They start on a vertex adjacent to the bridge on one side and end on a vertex adjacent to the bridge on the other side.
none

12.41
1.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. An Euler trail uses every edge exactly once.

It does not need to start and end on the same vertex.

This is a Hamilton path. It is not an Euler trail because it does not use every edge. It does not use bc or ae.

Hamilton path

2.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. An Euler trail uses every edge exactly once.

This is an Euler trail since it visits every edge exactly once. It is not a Hamilton path since it visits vertices more than once.

Euler trail

3.

A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. An Euler trail uses every edge exactly once.

This is neither. It does not visit every edge nor does it visit every vertex.

neither

12.42
1.

A brute force algorithm lists every possible solution and then compares them to find the best possible solution. This scenario is an example of the brute force algorithm.

The greedy algorithm chooses the best choice at every branch of the path, continuing to make the best choice at each stage and finally linking those choices together into an overall solution. The greedy algorithm can miss the best choice, but sometimes does find it.

Since you used the brute force algorithm, you are sure to find the best solution, but it does take a long time.

brute force algorithm

12.43
1.

V → W → X → Y → Z → V

V → W → X → Z → Y → V

V → W → Y → X → Z → V

V → W → Y → Z → X → V

V → W → Z → X → Y → V

V → W → Z → Y → X → V

V → X → W → Y → Z → V

V → X → W → Z → Y → V

V → X → Y → W → Z → V

V → X → Y → Z → W → V (reverse of 6)

V → X → Z → W → Y → V

V → X → Z → Y → W → V (reverse of 4)

V → Y → X → W → Z → V

V → Y → X → Z → W → V (reverse of 5)

V → Y → W → X → Z → V

V → Y → W → Z → X → V (reverse of 11)

V → Y → Z → X → W → V (reverse of 2)

V → Y → Z → W → X → V (reverse of 8)

V → Z → X → Y → W → V (reverse of 3)

V → Z → X → W → Y → V (reverse of 15)

V → Z → Y → X → W → V (reverse of 1)

V → Z → Y → W → X → V (reverse of 7)

V → Z → W → X → Y → V (reverse of 13)

V → Z → W → Y → X → V (reverse of 9)

12.44
1.

To be sure you find the shortest route, you need to find the length of all possible routes.

Since there are 4 vertices, there are $\left( {4{\text{ }}-{\text{ }}1} \right)!{\text{ }} = {\text{ }}3!{\text{ }} = {\text{ }}3 \cdot 2 \cdot 1 = 6$ possible cycles, but half of them will be the reverse of the others.

T = Travis, B = Beal, E = Edwards, L = Los Angeles

Route TB BE EL LT Sum

Distance 84 410 106 396 996

Route TE EB BL LT Sum

Distance 370 410 439 396 1,615

Route TB BL LE ET Sum

Distance 84 439 106 370 999

The other three routes are the reverse of these three cycles.

The shortest route is from Travis to Beal to Edwards to Los Angeles Air Force Bases, and then return to Travis.

The officer should travel from Travis Air Force Base to Beal Air Force Base, to Edwards Air Force Base, to Los Angeles Air Force Base, and return to Travis.

12.45
1.
D → B → E → A → C → F → D; 550 min or 9 hrs 10 min.

12.46
1.

The star topology and the tree topology are trees. They are connected and have no cyclic subgraphs.

The ring topology is not a tree. It forms a cycle.

The mesh topology is not a tree. It has cyclic subgraphs.

The star topology is a tree, and the tree topology is a tree. The ring topology and the mesh topology are not trees because they contain cycles.

12.47
1.

The star topology is a star tree.

A star tree is a tree that has exactly one vertex of degree greater than 1 called a root, and all other vertices are adjacent to it.

star topology

2.

The tree topology is a caterpillar tree.

A caterpillar tree is a tree that has a central path that can have vertices of any degree, with each vertex not on the central path being adjacent to a vertex on the central path and having a degree of one.

tree topology

3.
There is no topology that has a path graph configuration. A path graph or linear graph is a tree graph that has exactly two vertices of degree 1 such that the only other vertices form a single path between them, which means that it can be drawn as a straight line.
none

12.48
1.

Removing ji breaks the tree into two separate components so that it is no longer a tree.

One component: g, h, i, j

The other component: k, l, m

Vertices k, l, and m are in one component, and vertices g, h, i, and j are in the other.

2.

The number of edges in a tree graph with n vertices is n – 1.

This graph has 6 vertices and 5 edges. This is what the formula predicts for a tree graph with 6 vertices. If n is 6, then n – 1 is 5.

There are 6 vertices and 5 edges, which confirms Graph I is a tree, because the number of edges is one less than the number of vertices.

3.
If you add edge cf, then you will have a quadrilateral (b, c, f, e).
a quadrilateral

12.49
1.
a To be a spanning tree of another graph, N₁ must be a subgraph of the Graph H. It cannot be a subgraph if the edge sq is not in Graph H.
True

2.
b A spanning tree cannot contain a cycle. This graph contains a triangular cycle (r, s, t).
False

3.
a All the vertices are included, the graph is connected, and there are no cycles. Also, no vertices are adjacent that were not adjacent in Graph H.
True

4.
a This graph is not connected. A spanning tree is a connected graph.
True

12.50
1.
Answers may vary. Here are three possible spanning trees of Graph J:

12.51
1.

Remember that the number of edges in a tree graph with n vertices is n – 1.

Graph V has 9 vertices and 11 edges. The associated spanning tree will have 8 edges. You need to remove 3 edges from Graph V.

The example removed ac, cf, and be.

You want to form a spanning tree by removing three edges. Keep in mind that you have to break up the three cycles, since a spanning tree cannot have any cycles.

The three edges must include one edge from list A and a pair of edges from list B.

List A: be, eh, hi, gi, bg

List B: ac and ad, ac and af, ac and cd, ac and cf, ad and af, ad and cd, ad and cf, af and cd, af and cf, or cd and cf

The three edges must include one edge from list A and one pair of edges from list B.
List A: be, eh, hi, gi, bg
List B: ac and ad, ac and af, ac and cd, ac and cf, ad and af, ad and cd, ad and cf, af and cd, af and cf, or cd and cf.

12.52
1.

Rank the weights: 24, 37, 45, 49, 68, 68, 89

Step 1: Choose the edge with the minimum weight of all the edges.

VY has a weight of 24.

Step 2: Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.

UW has a weight of 37.

Step 3: Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.

WX has a weight of 45.

Step 4: Repeat Step 3 until all the vertices of the original graph are included and you have a spanning tree.

UX has a weight of 48. UX would create a cycle, so do not use it.

Repeat Step 3: Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.

There are two edges with a weight of 68. You can put either in your graph. VW or YX (not both)

You are done. You now have five vertices in your graph.

Add the weights: ${\text{24 + 37 + 45 + 68 = 174}}$

The weight of your spanning tree is 174.

There are two possible minimum spanning trees, each with a total weight of 174:

Check Your Understanding

1.
a True

2.
b Think of a graph that represents a map where the districts are vertices and edges represent shared borders. Suppose a district was an entire island. The island would have no shared borders. It would be an isolated vertex in the graph to represent a map. It would have degree 0 since no edges would be shared with another vertex.
False

3.
a True

4.
b A multigraph can have loops or double edges that allow a graph with three vertices to have more than three edges.
False

5.
b It could be adjacent, but it does not have to be. Picture the numbers 1, 2, and 3 on a ruler as being vertices. Draw an edge between 1 and 2. Draw another edge between 2 and 3. The numbers 1 and 2 are adjacent. The numbers 2 and 3 are adjacent. But the numbers 1 and 3 are not adjacent.
False

6.
b In a complete graph, each vertex is adjacent to every other vertex. The number of edges in a complete graph with n vertices is the sum of the whole numbers from 1 to n – 1. For instance, in an example in the lesson, a complete graph with 6 vertices had 15 edges.
False

7.
a A cycle is a series of connected edges that begins and ends at the same vertex but otherwise never repeats any vertex. All vertices must be of degree 2.
True

8.
b Some graphs have no edges.
False

9.
a The vertex where you begin is not important, but you must list vertices sequentially. However, it will help you keep track if you start with the letter that comes earliest in the alphabet.
True

10.
b The vertex where you begin is not important, but you must list vertices sequentially. The cycles do not take the same path from b to d.
False

11.
a True

12.
The sum of the degrees is always double the number of edges, which means it has to be an even number, but 13 is odd.

13.

If n is the number of vertices in a complete graph, then each vertex is connected to n – 1 other vertices (i.e., has degree n – 1).

The total number of degrees for the graph is thus $n\left( {n - 1} \right)$ .

By the Sum of Degrees Theorem, ${\text{the number of edges = }}\frac{{{\text{sum of degrees}}}}{2} = \frac{{n\left( {n - 1} \right)}}{2}$ .

The last expression is equivalent to what the student said. $\frac{n}{2}\left( {n - 1} \right)$

Yes. If n is the number of vertices in a complete graph, the number of edges is $\frac{{n(n - 1)}}{2} = \frac{n}{2}(n - 1)$ which is half the number of vertices times one less than the number of vertices.

14.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

always true

15.

There can be no complete correspondence between vertices.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

never true

16.
The two graphs could be isomorphic. You could also have the graphs not be isomorphic. The sum of degrees could be 6 on both graphs. One could have three vertices of degree 2. The other graph could have two vertices of degree three.
sometimes true

17.

There can be no complete correspondence between the edges.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

never true

18.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

always true

19.
There is often more than one isomorphism between two isomorphic graphs, but not always.
sometimes true

20.

They could be isomorphic, but not always. This is an example of when they are not isomorphic.

You could have two vertices in Graph 1 and two vertices in Graph 2. In Graph 1, the vertices share one edge. In Graph 2, the vertices share two edges. The vertices in Graph 1 have degree one, and the vertices in Graph 2 have degree 2. The graphs are not isomorphic.

sometimes true

21.

This is opposed to the definition of isomorphism.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

never true

22.
sometimes true

23.

The correspondence between their vertices ensures that the sum of their degrees will be the same.

Two graphs are isomorphic if either one of these conditions holds:

One graph can be transformed into the other without breaking existing connections or adding new ones.

There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

always true

24.
One way to find the complement of a graph is to draw the complete graph with the same number of vertices and remove all the edges that were in the original graph.
always true

25.
All paths are trails, but not all trails are paths. Some trails use the same vertex more than once. A path has no repeated vertices.
sometimes true

26.
All trails are walks. Trails use connected vertices, which is what it takes to be a walk.
always true

27.
All paths are walks, but not all walks are paths. Some walks use the same vertex more than once. A path has no repeated vertices.
sometimes true

28.
By definition, a circuit is a trail that begins and ends at the same vertex.
always true

29.
By definition, a directed cycle is a path that begins and ends at the same vertex.
always true

30.

By definition, a directed cycle is a path that begins and ends at the same vertex. A circuit begins and ends at the same vertex.

A directed cycle does not necessarily start and end at the same vertex, so not all directed cycles are circuits.

sometimes true

31.

By definition, a directed cycle is a path that begins and ends at the same vertex.

A circuit is a trail that begins and ends at the same vertex. Thus, a directed cycle is a circuit.

always true

32.
You could color a graph with more colors than the minimum number required. For instance, you could use a different color for every vertex on a quadrilateral cycle. This graph would have a chromatic number of 2 but use 4 colors.
sometimes true

33.
This is the definition of the chromatic number.
always true

34.
always true

35.
has no repeated egdes

36.
is closed

37.
has no repeated vertices

38.
has no repeated edges

39.
$n$

40.
at least

41.
A component of a graph is a subgraph in which there is a path between each pair of vertices in the subgraph, but no edges between any of the vertices in the subgraph and a vertex that is not in the subgraph. A disconnected graph will have at least two components.
never true

42.
A graph might have two components whose vertices all have even degrees. It might be composed of a single component of even-degreed vertices.
sometimes true

43.
The graph of the town had four vertices with odd degrees. To have an Euler circuit, you need the vertices to be of even degree.
never true

44.
A graph might have two components whose vertices all have even degrees. If the graph is not connected, it cannot have an Euler circuit. It might be composed of a single component of even-degreed vertices and have an Euler circuit.
sometimes true

45.
Euler proved that for a graph to have an Euler circuit, all the vertices must be even.
always true

46.
By definition, an Euler circuit is a circuit (closed trail) that visits every edge in a graph exactly once.
always true

47.
Sometimes an Euler circuit visits the same vertex more than once, and sometimes it does not. If the vertex has degree 4, it will be visited twice, for instance.
sometimes true

48.
You cannot add edges between vertices that were nonadjacent.
never true

49.
This is the correct procedure to eulerize a graph.
always true

50.
You might have an odd number of vertices with odd degrees. For instance, if there are three vertices with an odd degree, you cannot add 1.5 edges.
sometimes true

51.
edge

52.
Fleury’s

53.
circuit, trail

54.
components

55.
local bridge

56.
bridge

57.
vertex

58.
complete

59.
A circuit is a trail that begins and ends at the same vertex. A trail does not repeat an edge. A Hamilton cycle is a circuit because it begins and ends on the same vertex and does not repeat an edge.
is

60.
An Euler circuit visits every edge exactly once. A Hamilton cycle visits every vertex exactly once. A Hamilton cycle that visits every edge is also an Euler circuit. Some Hamilton cycles are Euler circuits, but not all. Some Euler circuits are Hamilton cycles, but not all.
is

61.
A cycle begins and ends at the same vertex. A circuit begins and ends at the same vertex but has no repeated edges. Since adding the name “Hamilton” means no repeated vertices, Hamilton cycles and Hamilton circuits are equivalent.
is not

62.
is

63.
To find the weight of a trail, add the weights of each edge visited along the way.
is

64.
A weighted graph can be any kind of graph, complete or not complete. A weighted graph just means that numbers are assigned to each edge, usually associated with a real-world application.
is not

65.
The number of ways to arrange n distinct objects is n!.
is not

66.
A cycle begins and ends at the same vertex. A circuit begins and ends at the same vertex but has no repeated edges. A cycle might or might not have repeated edges.
is not

67.
A Hamilton path does not need to begin and end on the same vertex.
different from

68.
A Hamilton path does not need to begin and end on the same vertex. It does need to visit every vertex exactly once. While making that happen, the number of vertices listed will always be the same as the number of vertices in the graph.
the same as

69.
A path that visits each vertex exactly once is a Hamilton path. Recall that a path is a walk that has no repeated vertices or edges. An Euler trail uses every edge exactly once. It is only logical that the methods of finding them would be different since you have different goals.
different from

70.
If a graph has a bridge, the start of a Hamilton path will be on one side of the bridge, and the ending vertex will be on the other side of the bridge. You will avoid crossing the bridge until you have no other choice.
different from

71.
b This is a Hamilton path.
False

72.
b The graph might be disconnected.
False

73.
b This graph may have a Hamilton path that starts on one cycle on a vertex adjacent to p and ends on p. It can go around the first cycle, cross to the second cycle at p, and then go around the second cycle.
False

74.
a A Hamilton path could be done, but not one beginning and ending at the ends of the bridge. If a bridge exists, it must be avoided until it is the last choice.
True

75.
a
A brute force algorithm lists every possible solution and then compares them to find the best possible solution. This can take a lot of time when in the real world there can be many choices.

The greedy algorithm chooses the best choice at every branch of the path, continuing to make the best choice at each stage and finally linking those choices together into an overall solution. This might miss the best possible solution overall but is much faster than the brute force algorithm.

True

76.
b A brute force algorithm lists every possible solution and then compares them to find the best possible solution. This can take a lot of time but will always find the ideal solution.
False

77.
b
A brute force algorithm lists every possible solution and then compares them to find the best possible solution. This can take a lot of time when in the real world there can be many choices.

The nearest neighbor algorithm chooses the best choice at every branch of the path, continuing to make the best choice at each stage and finally linking those choices together into an overall solution. This might miss the best possible solution overall but is much faster than the brute force algorithm.

False

78.
b
A brute force algorithm lists every possible solution and then compares them to find the best possible solution. This can take a lot of time when in the real world there can be many choices.

The greedy algorithm chooses the best choice at every branch of the path, continuing to make the best choice at each stage and finally linking those choices together into an overall solution. This might miss the best possible solution overall but is much faster than the brute force algorithm.

False

79.
a A brute force algorithm lists every possible weighted Hamilton cycle and then compares them to find the cycle with the least weight.
True

80.
b The nearest neighbor algorithm chooses the best choice at every branch of the path, continuing to make the best choice at each stage and finally linking those choices together into an overall solution. This might miss the best possible solution overall but is much faster than the brute force algorithm.
False

81.
b The traveling salesman problem is the shortest route to travel to multiple points and return to the original location.
False

82.
a True

83.
a True

84.
b
The number of distinct Hamilton cycles of a complete graph with n vertices is $\left( {n - 1} \right)$ !.

Since half of those cycles are the reverse of the others, there are only $\frac{{\left( {n - 1} \right)!}}{2}$ distinct weighted cycles.

False

85.
b A spanning tree has no cycles. By definition, a spanning tree is acyclic.
False

86.
a A spanning tree has no cycles. By definition, a spanning tree is acyclic. Since it has no cycles, it has no triangles.
True

87.
a By definition, a spanning tree must span the whole graph by visiting every vertex of a graph.
True

88.
a Spanning trees are connected, acyclic, and visit every vertex in a graph. They are the unique path that visits every vertex in a graph.
True

89.
a All trees are connected.
True

90.
b Kruskal’s algorithm is a method of finding a minimum spanning tree of a weighted graph, not for finding all the different spanning trees.
False

91.
b In examples in the lesson, you found the spanning tree for graphs with cyclic subgraphs.
False

92.
a Kruskal’s algorithm is a method of finding a minimum spanning tree of a weighted graph. It can be used in practical applications such as finding the most economical way to install a computer network.
True

93.
a Kruskal’s algorithm is a method of finding a minimum spanning tree of a weighted graph. The tree it finds includes every vertex of the original graph with the least weights that do not create a cycle.
True

94.
a A cut edge is another term for a bridge. If you delete the cut edge from the spanning tree, the graph is no longer connected. Thus, you cannot delete the cut edge/bridge from the spanning tree or the graph is no longer connected. A spanning tree must be connected.
True

Chapter 12

Your Turn

Check Your Understanding