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.
Suppose the graph has no vertices of degree 1.
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$.
But the graph is assumed to be finite, so we have a contradiction. Hence there is a vertex of degree 1.
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.