Question: Suppose that G is a graph such that any two vertices in G that have the same degree are not connected to any of the same vertices. In other words, vertices with the same degree don't share any common vertices in the set of edges. Assume that there are at least two vertices in G. Show that there is a vertex degree 1.
I'm a bit stuck on this problem. I'm assuming it's implied that there's at least 1 edge in the graph. My initial approach is to use the Pigeonhole principle. The possible degrees in a graph G with $n$ vertices are $0,1,2,...,n−1$. But that's complicated by the fact that any vertices of the same degree don't share mutual vertices. At the most I think that potentially splits the graph into halves, but then we have the think about the vertices they're connected to. So I'm not entirely sure how to go about proving this. I was thinking induction might be useful, but I'm not entirely sure how to include this property of the graph in such a proof.
Any advice would be greatly appreciated.