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$:

enter image description here

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

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

  • 2
    $\begingroup$ Does this assume the graph is connected? $\endgroup$ Dec 4 '21 at 20:43
  • 1
    $\begingroup$ It is enough to assume that there is at least one non-isolated vertex. $\endgroup$
    – kabenyuk
    Dec 5 '21 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.