chivistaelmore

2022-07-18

Let G be a graph of two or more vertices. Prove by contradiction that
(All u,v vertices in G, $N\left(u\right)=N\left(v\right)$)
(All x vertex in G, $N\left(x\right)=$ {})
(Hint: N(u) denotes the neighbourhood of vertex u; i.e. N(u) is the set of every vertex v such that u and v are neighbours.)
Solution:
(All u,v vertices in G, $N\left(u\right)=N\left(v\right)$) and (Exist x, y vertices in G, $N\left(x\right)!=$ {} and so y is in N(x))
$=>\left\{N\left(x\right)=N\left(y\right)\right\}$
(Exist y vertex in G, y in N(y))
{from definition of neighbourhood: (All z vertex in G, not (z in N(z))}
F
I'm confused. It looks like the problem is telling me that each vertex in G shares the neighbourhood with each other vertex, that the graph is complete. From that I have to prove that for all vertexes in G, the neighbourhood is empty? I'm very confused, could someone explain the question better and walk me through the process?

kitskjeja

Expert

Step 1
The crux of the contradiction is that N(x) does not contain x.
If x and y are neighbors, then $x\in N\left(y\right)$ and $y\in N\left(x\right)$. Therefore it is impossible for $N\left(x\right)=N\left(y\right)$ to hold, because x is N(y) but not in N(x).
Step 2
Phrased differently, if $N\left(u\right)=N\left(v\right)$ for any pair of vertices u,v, then no pair of vertices can be neighbors.

Do you have a similar question?