Chapter 12: Graph TheoryContent check — Contemporary Math, Chapter 12: Graph Theory

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.

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.

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

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.

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

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.

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}$.

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.

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.

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.”

Entry 3 in Row 13 is 286.

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)$

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.

• 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.

• 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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}.

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.

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.

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

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.

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 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.

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 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$

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$

Add the weights of the individual edges.

The total weight of the Hamilton cycle is 26.

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.

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.

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.

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

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.

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.

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.

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.

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.

1. V → W → X → Y → Z → V

2. V → W → X → Z → Y → V

3. V → W → Y → X → Z → V

4. V → W → Y → Z → X → V

5. V → W → Z → X → Y → V

6. V → W → Z → Y → X → V

7. V → X → W → Y → Z → V

8. V → X → W → Z → Y → V

9. V → X → Y → W → Z → V

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

11. V → X → Z → W → Y → V

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

13. V → Y → X → W → Z → V

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

15. V → Y → W → X → Z → V

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

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

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

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

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

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

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

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

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

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-1\right)!=3!=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

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 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 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.

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.

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

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.

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

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.