MAD 3105 Assignment 06

 

 

MAD 3105 Assignment 06                                               NAME:_________________________________________________ Connectivity and                                   DUE: Thursday, February 27, 2025 (11:59pm EST) Euler & Hamilton Circuits; Cut Vertices & Cut Edges

 

Directions: See Canvas. Do all work individually without outside help. 50 points total.

 

(1) (10 points)

Find the number of paths of length 3 from 𝑑 to 𝑐 in the graph shown to the right. Use Theorem 2 on pg 688 (Rosen pdf, 7th ed.) pg 723 (Rosen, 8th ed.) Show each matrix, 𝑨,𝑨𝟐,𝑨𝟑. Order vertices in the matrices as 𝑎,𝑏,𝑐, 𝑑. See Discussions to check that you have matrix 𝐴 correct.

 

 

 

The entry at A3[4,3]A^3[4,3]A3[4,3] (row d, column c) is 4, so there are 4 paths of length 3 from d to c.

              

(2) (5 points each)

For the given graph to the right, find all (if any)

(a)  cut vertices. For credit either show why by graphing and describing the resulting subgraph, or explain why there are no cut vertices.

The only cut vertex is d, since removing it disconnects c from a and b.

(b) cut edges. For credit either show why by graphing and

describing the resulting subgraph, or explain why there are no cut edges.

The only cut edge is (d, c), since removing it disconnects c from the rest of the graph.

(3) (10 points)

Determine whether or not the graph 𝐺1 to the right has an Euler Circuit. If so, find such a circuit (list the circuit by using the sequence of vertices, rather than the edge notation).

 

 

 

 

Graph for problem 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Graph for problem 2

·       Euler circuit exists if all vertices have even degree.

·       Checking degrees: a=3, b=3, c=3, d=3, e=4.

·       Since a,b,c,d have odd degrees, no Euler circuit exists.

 

 

 

(4) (4 points/4 points/6 points)

For the given graph (to the right), determine:

(a)  whether the conditions for Dirac’s theorem are satisfied. Explain why they are or are not.

Dirac’s Theorem: Each vertex must have deg(v) ≥ n/2 (i.e., deg ≥ 5/2). Here, deg(a)=2, which is less than 5/25, so Dirac’s Theorem does not apply.

(b)  whether the conditions for Ore’s theorem are satisfied. Explain why they are or are not.

Ore’s Theorem: The sum of degrees for every non-adjacent pair must be ≥ n.

·       Checking: deg(a)+deg(e)=2+2=4, which is less than 5.

·       So, Ore’s Theorem does not apply.

 

(c) whether the graph has a Hamilton circuit. If so, give a Hamilton circuit.

Hamilton Circuit: Since the graph forms a cycle (a → b → c → e → d → a), it has a Hamilton circuit:
a→b→c→e→d→a.

 

(5) (6 points)

Determine whether each graph below (graphs 𝐺 𝑎𝑎𝑑 𝐻) are strongly connected or just weakly connected. For credit explain why.

 

 

 

 

 

There is a directed path from every vertex to every other vertex in both directions.

Since every vertex has a path to every other vertex, G is strongly connected.

Since not all vertices have directed paths in both directions, H is not strongly connected.