I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever).

The problem statement is as such:

If A and B are friends, and B and C are friends, then A and C are friends too.

In a simple network like the following, this makes complete sense:

1 — 2 — 3

Analysis:

We can see that 1 and 2 are friends, and 2 and 3 are friends. It follows from the problem statement that 1 and 3 must be friends too. This is the most generic case for a problem like this.

Where I get confused is in a following network:

1 — 2 — 3 — 4

Analysis:

We can see that 1 and 2 are friends, and 2 and 3 are friends; therefore, 1 and 3 must be friends. Also, since 2 and 3 are friends, and 3 and 4 are friends; therefore, 2 and 4 must also be friends.

Since 1 and 2 are already friends, would it follow from our conclusion of the last sentence (that 2 and 4 are friends) that 1 and 4 must also be friends?

Moving forward into a bigger picture, any group of connected nodes would also all be friends?

What’s the best way to analyze this?