Let K2,2 be a complete bipartite graph given below. Which of the following is…

Concept

In graph theory a path is a walk in which no vertex is repeated; its length is its number of edges. A walk of length k allows vertices (and edges) to repeat, and the count of walks of length k between two vertices equals the [u][v] entry of the k-th power of the adjacency matrix. So "number of paths" and "number of walks" are different quantities, and a path of length 3 must visit 4 distinct vertices.

Setup

The complete bipartite graph K2,2 has parts V1 = {1, 2} and V2 = {3, 4}, with every left vertex joined to every right vertex. Its edges are 1-3, 1-4, 2-3 and 2-4. Because edges only go between the two parts, any path must alternate sides at every step.

Application

A path of length 3 from 1 to 4 uses 4 distinct vertices in the order 1, x, y, 4. Trace the alternation:

1. From 1 the first step must cross to the right part: the neighbours of 1 are 3 and 4. It cannot be 4 (that is the destination and would leave only 2 edges, repeating vertex 4), so the second vertex is 3.

2. From 3 the next step crosses back to the left part: neighbours of 3 are 1 and 2. Vertex 1 is already used, so the third vertex is 2.

3. From 2 the last step crosses to the right part to reach 4: 2-4 is an edge, completing 1 → 3 → 2 → 4.

No other choice of distinct intermediate vertices works, so exactly one simple path of length 3 exists: 1 → 3 → 2 → 4. Hence the count is 1.

Cross-check

Counting walks instead (allowing repeats) gives four: 1→3→1→4, 1→3→2→4, 1→4→1→4 and 1→4→2→4 — this is the adjacency-matrix value A3[1][4] = 4. Three of these repeat a vertex, so they are walks, not paths. Removing them leaves the single simple path, confirming the answer is 1.