## Transitivity and Paths

Chapters > Graphs

Now our graph contains two edges, (Joan,Bob) and (Bob,Melanie). Do we have sufficient information to complete our task? The answer is: "Yes".

To obtain a solution, we apply the rule of transitivity

Given two edges (a, b) and (b,c), the transitivity rule implies that (a,c) is also an edge

and deduce that (Joan,Melanie) is also an edge because (Joan,Bob), and (Bob,Melanie) are edges, meaning Joan is older than Melanie, or Melanie is younger than Joan (edges are bidirectional). We add the edge (Joan,Melanie) to the graph. Task accomplished.

In general, transitivity is a recipe to apply deduction on chains (paths) of edges. To build a path

- Start with an edge
- If the tail of the next edge is the same as the head of the last edge on the path, add the edge to the end of the path
- Proceed with the next edge, until all edges of the graph are exhausted

Starting with the node (Joan,Bob) and applying this procedure to our graph, we obtain the path [(Joan,Bob), (Bob,Melanie)], or [Joan, Bob, Melanie] in short.

Due to transitivity, all nodes on a path are related to each other, even if they are not adjacent. Because Joan and Melanie are on the path, we can decide that they are related (connected), and creating an edge (Joan,Melanie) is legitimate.