vertex u and v connected via an edge implies $C(u)=C(v)$

115 Views Asked by At

Recall that a graph G is called connected if any two of its vertices are connected, otherwise, it is disconnected.

Definition: $C(u)$ denotes the set of all vertices v in a graph G that are connected to u (via edges).

Claim:

Suppose that there is a path from u to v; or u-v exists. Then, $C(u)=C(v)$

Suppose for simplicity that the edge $e_{uv}$ connects the vertex u and v. $C(u)=v$ and $C(v)=u$

But this implies $C(u) \neq C(v)$

Any help is appreciated. Thanks in advance.

1

There are 1 best solutions below

3
On BEST ANSWER

You cannot write $C(u)=v$ since LHS is a set and RHS is a vertex. Ditto $C(v)=u$.

What you mean to say is that $v \in C(u)$ and $u \in C(v)$. From here you can conclude (after some argument) that indeed $C(v) = C(u)$. Can you prove it?