Graph with a pendant vertex
I am trying to prove the following statement but cannot make a first step forward.
$\endgroup$ 4If $G$ is a simple graph in which neighbours of an arbitrarily chosen vertex have different degrees, then $G$ has a pendant vertex.
2 Answers
$\begingroup$First handle the case that there are no edges (the truth in this case depends on exactly how you specify the problem; your first statement is ambiguous/incorrect; your second statement (in the comment) makes it untrue for these graphs, since there are no two neighbours of one vertex with the same degree, but there is no pendant vertex).
Use following proof for all other cases.
Assume there is no vertex of degree 1. Let $v$ be a vertex of maximum degree $k$. Since there is at least one edge this means $k\geq 2$. The $k$ neighbours of $v$ now all must have different degrees at most $k$ and at least 2, which is impossible by the pigeonhole principle.
$\endgroup$ $\begingroup$Consider a square $ABCD$ with four edges, and toss in an extra (curved) edge from $A$ to $B$. Then every vertex has neighbors with degrees 2 and 3, but there's no pendant vertex. So clearly your proof will depend on some property of "graphs" that's at least somewhat subtle: must there be at most one edge between any two vertices?
Even if you rule out that case, take an octagon, and add a self-loop at vertices 1, 2, 5, 6. Maybe "loops" aren't allowed either.
But as this must make clear, you really need a clear definition here.
$\endgroup$ 1
