4.5.2. Degree of Vertices in Cartesian Product

In this section, we define the Cartesian product of two graphs G₁ and G₂. The vertex set of the Cartesian product will be the ordered pairs (u, v), where u is a vertex from G₁ and v is a vertex from G₂.

The Cartesian product of two graphs combines their vertex sets into pairs. If you have a vertex u from graph G₁ and a vertex v from graph G₂, that pair (u, v) becomes a vertex in the new graph. This means that you will have a vertex for every possible combination of a vertex from G₁ and a vertex from G₂, which results in the ordered pairs forming the new vertex set.

Imagine you are organizing a team of employees where one graph represents their skills (G₁) and the other represents their projects (G₂). The Cartesian product helps you identify each employee and the project they are working on, pairing each employee's skill with their project, similar to pairing ingredients to create a specific dish.

Vertices (u₁, v) and (u₂, v) are connected by an edge if u₁ and u₂ are adjacent in G₁. Similarly, (u, v₁) and (u, v₂) are connected if v₁ and v₂ are adjacent in G₂.

To determine if two vertices in the Cartesian product are connected by an edge, we have two possible conditions. First, if both vertices share the same second component (v) and have connections in the first graph (G₁), then they will be connected. Second, if both vertices share the same first component (u) and have connections in the second graph (G₂), they will also be connected. This ensures that we're preserving the adjacency relationships from both graphs when forming the Cartesian product.

Think of this as forming relationships between students and their classes. If Student A (u₁) and Student B (u₂) both attend the same math class (v), they can be connected because they share that class. Another example is if two students from distinct classes can work on the same project, the connections represent their collaboration opportunities.

The cardinality of the edge set for the Cartesian product of the graphs is calculated using the formula |E(G₁ × G₂)| = |E(G₁)| |V(G₂)| + |E(G₂)| |V(G₁)|.

To find the total number of edges in the Cartesian product of two graphs, we can use a formula derived from the definitions of edges in the product. The first part of the formula counts edges that arise from vertices of G₁ linked to all vertices of G₂, while the second part counts edges for the opposite direction. Essentially, for every edge in G₁, each vertex in G₂ participates in the product; similarly for G₂ with vertices in G₁.

Consider a factory that produces different models of cars (G₁) and different colors (G₂). Each model is designed in various colors, creating edges between models and colors. If there are 3 models and each model can be in 4 colors, you can expect 12 unique combinations, as each model (edge) connects to every color (vertex), illustrating how the product creates numerous combinations.

The degree of a vertex (u, v) in the Cartesian product is the sum of the degrees of u in G₁ and the degree of v in G₂: deg(u, v) = deg(u) + deg(v).

To find the degree of a vertex in the Cartesian product, we look at how many connections (or edges) it has from both constituent graphs. This means that the degree of the vertex (u, v) incorporates how many edges are linked to vertex u in graph G₁ and how many edges are linked to vertex v in graph G₂. If u is connected to several vertices in G₁ and v is connected to several vertices in G₂, then their sum gives you the required degree of (u, v).

Think of a social network where each person (vertex u) has friends and belongs to particular groups (vertex v). The total connections someone has correlates not just to their individual friends but also how many groups they belong to. Counting all their connections to friends (in graph G₁) and groups (in graph G₂) gives a complete picture of their network degree.

--