I'm studying for discrete math and I'm looking for my professor's test problems and their solutions. There is one in particular I am having trouble conceptualizing, maybe someone could help me out.
8. Let G be a graph of two or more vertices. Prove by contradiction that
(All u,v vertices in G, N(u) = N(v))
=> (All x vertex in G, N(x) = {})
(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(u) = N(v)) and
(Exist x, y vertices in G, N(x) != {} and so y is in N(x))
=> {N(x) = N(y)}
(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?
Thanks!
The crux of the contradiction is that $N(x)$ does not contain $x$.
If $x$ and $y$ are neighbors, then $x \in N(y)$ and $y \in N(x)$. Therefore it is impossible for $N(x)=N(y)$ to hold, because $x$ is $N(y)$ but not in $N(x)$.
Phrased differently, if $N(u)=N(v)$ for any pair of vertices $u,v$, then no pair of vertices can be neighbors.