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)) =&gt; { 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))}FI'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?

Question

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))  =&amp;gt;  {  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))}FI&#039;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&#039;m very confused, could someone explain the question better and walk me through the process?

kitskjeja · Accepted Answer

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