Graph theory problem for non-trivial graphs with n vertices.

I stumbled upon this question about graphs, and I am unable to think of a way to solve it.

This is a question: Let G be a non-trivial graph containing at least one edge. Prove that, if each two vertices of the same degree don't contain a common neighbor, that then G contains end vertex (vertex with degree 1).

I am having trouble even starting, I need a proper way to think of how to solve these type of questions.

• what does "contains end vertex" mean? Commented Jan 20, 2020 at 10:34
• A vertex with degree 1 (leaf vertex). Commented Jan 20, 2020 at 10:37
• I edited the question. The vertices must have the same degree. Commented Jan 20, 2020 at 10:50

The graph has at least one edge, so it has a vertex $$A_1$$ of degree at least 2. The vertices joined to $$A_1$$ by an edge must all have different degrees, so at least one of them, say $$A_2$$, has degree at least 3.
We can now repeat this argument indefinitely. Having found a vertex $$A_n$$ with degree at least $$n+1$$, we know that the $$\ge n+1$$ neighbours of $$A_n$$ all have different degree and each of their degrees is at least 2. So one of them, $$A_{n+1}$$ must have degree at least $$n+2$$.
For completeness, we should show that it is possible to have a graph of $$n$$ vertices satisfying the condition. The easiest example is where there is just one edge.