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.)

chivistaelmore

chivistaelmore

Answered question

2022-07-18

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?

Answer & Explanation

kitskjeja

kitskjeja

Beginner2022-07-19Added 13 answers

Step 1
The 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 2
Phrased differently, if N ( u ) = N ( v ) for any pair of vertices u,v, then no pair of vertices can be neighbors.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?