# Showing there is a node in the graph with one and only one edge

We have an undirected simple graph with $$n$$ vertices where for every pair of vertices $$v_1,v_2$$, if $$d(v_1)=d(v_2)$$ then the set of neighbours of $$v_1$$ is disjoint from the set of neighbours of $$v_2$$. Assuming the graph contains at least one edge, prove that there is a vertex of degree exactly $$1$$ in the graph.

For example the following graph has vertices of degree exactly $$1$$:

While this problem concerns a graph, I feel like there is a way to apply pigeonhole theory to prove this. Is this possible?

• I placed some edits with more technical terms to make the question more clear. Do check whether this is really what you meant. Dec 4 '21 at 7:31
• Wouldn't this be false if the graph consists of $n$ isolated vertices? Dec 4 '21 at 7:48
• @VTand that's true. But, I guess, the OP is talking about connected graphs only. Can you find a counterexample in connected graphs? Dec 4 '21 at 13:40
• @VTand but there is at least one edge in the graph Dec 4 '21 at 20:42
• @SayanDutta i appreciate the edits, thank you Dec 4 '21 at 20:50

Let $$v$$ be the vertex of the greatest degree and let $$\operatorname{deg}(v)=k>0$$. Let $$N(v)$$ be neighbors of vertex $$v$$. Then the degrees of all vertices from $$N(v)$$ are pairwise distinct, and if there are no vertices of degree 1 among them, then there must be a vertex of degree $$k+1$$ or more. This contradicts the choice of vertex $$v$$.