1

We're learning about Isomorphism, relations on graphs and graphs in general. I read this question in the book and this was the proof:

Clearly, a connected graph has a single component. On the other hand, any two vertices x, y in the same component of a graph G can be connected by a walk. Any walk from x to y of the shortest possible length must be a path.

I don't understand it 100% because i know that equivalence relations from Logic and set theory have to be reflexive, Symmetric and transitive but here it has another meaning. So can someone explain me both the proof and the relation on graphs?

question

1 Answers1

1

Here it has the same meaning. You are defining a relation on vertices of a (i assume undirected) graph.

Let $v \in V$. We have that $v$~$v$ since we have a path from a vertex to itself (the empty path). So i t is reflexive.

Let $v, u \in V$. If $v$~$u$ Then there is a path from $v$ to $u$. Inversely, if you walk that path from end to start, you get a path from $u$ to $v$, so $u$~$v$. So it is symmetric.

****Edit**: I wish to stress that this is only correct for undirected graphs.** In a directed graph it is possible to have a path from $u$ to $v$ without having a path from $v$ to $u$ and this fails. Now let $v, u, w \in V$ such that there is a path from $v$ to $u$ and from $u$ to $w$. This trivially means that there is a path from $v$ to $w$. Just go to $u$ and from there go to $w$. So $v$~$w$ which means transitivity.

So this is a equivalence relation.

Let's try to find the classes.

What is $[v]$? It is the set of all $u$ in $V$ such that there is a path from $v$ to $u$. this is just another way of saying "the component in which $v$ is in."

Oria Gruber
  • 12,739
  • It seems that the book the OP uses differentiates between paths and walks, where walks are allowed to use repeated edges, while paths are not (see, for instance, the quote about shortest possible length in the question post). This answer really means "walks" wherever it says "paths" (transitivity is a bit more fiddly if you use paths instead of walks). – Arthur Dec 12 '17 at 08:31
  • Well if a walk exists between $v$ and $w$ then they are in the same component, so there is also a path that connects them. – Oria Gruber Dec 12 '17 at 08:33
  • That is the extra fiddling I was talking about. My comment wasn't meant to you specifically, though. It was more of a caution to anyone reading this answer. – Arthur Dec 12 '17 at 08:35