Nós de baixo grau em gráficos esparsos

Deixei $G = (V,E)$ ser um gráfico tendo $n$ vértices, nenhum dos quais está isolado, e $n−1$ bordas, onde $n \geq 2$. Mostre que$G$ contém pelo menos dois vértices de grau um.

Eu tentei resolver esse problema usando a propriedade $\sum_{v \in V} \operatorname{deg}(v) = 2|E|$. Esse problema pode ser resolvido usando o princípio do buraco de pombo ?

Sim pode.

Você tem $n-1$ bordas, o que significa $2n-2$orifícios para pombos-nó. Se todo nó deve ter grau dois (ou mais), temos que colocar (pelo menos) dois pombos para cada nó, o que perfaz um total de$2n$ pombos.

Pelo referido princípio, (pelo menos) dois pombos não encontram um buraco solitário, o que significa que (pelo menos) um nó está isolado ou (pelo menos) dois nós têm apenas uma borda. Como nenhum nó é isolado por suposição, você tem (pelo menos) dois nós com grau um.

Como o número de arestas é $n-1$, o gráfico é uma árvore. Pegue um vértice inicial$v$ no $V(G)$. Agora comece a andar em qualquer direção e continue andando, sem repetir um vértice. Desde a$G$ é finito e não contém um ciclo, esse processo acabará parando em um vértice $u$ do grau 1. Se $v$também teve o grau 1, terminamos. Caso contrário, inicie uma nova caminhada em outra direção$v$. Essa caminhada também termina em um vértice de grau 1.