4.5.2. Degree of Vertices in Cartesian Product

Try these first

1. 1.

   Define the Cartesian product of two graphs.

   Hint

   Think about ordered pairs and pairs of vertices.

2. 2.

   What is the degree of a vertex?

   Hint

   Count the connections!

3. 3.

   What is the degree of vertex (u,v) in the Cartesian product?

   • deg(u) + deg(v)
   • deg(u) * deg(v)
   • deg(u) - deg(v)

   Hint

   Think about how the degrees interact together.

4. 4.

   If a graph G has no edges, what is the degree of all vertices?

   • True
   • False

   Hint

   Remember degrees count edges!

5. 5.

   Consider two graphs A and B where A has 3 vertices with degrees [0, 1, 2] and B has 3 vertices with degrees [1, 1, 1]. Calculate the degrees in the Cartesian Product.

   Hint

   Assess every pair in the product using the summed degrees.

6. 6.

   Given two graphs C and D, where C has a vertex of degree 4 and D with a vertex of degree 0, discuss the implications on the product graph's connectivity.

   Hint

   Consider how degree zero affects the overall performance in connectivity.