1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you so much! Is there same general idea on how I should be solving these types of problems. $\endgroup$
    – lastSheep
    Commented Jan 20, 2020 at 11:32
  • 1
    $\begingroup$ @lastSheep I cannot think of one. This is not a bookwork type question. But a good general rule is to look at simple cases first. I played with graphs of just a few points and soon realised that I kept being forced to add vertices with higher and higher degrees. $\endgroup$
    – almagest
    Commented Jan 20, 2020 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .