Hipótese de indução: Um grafo simples conexo e sem ciclos com vértices tem arcos.
Tese de indução:
Seja um grafo simples conexo e sem ciclos com vértices e provemos que tem arcos. Como não tem ciclos todo o arco é uma ponte.
Tiremos um arco a esse grafo. terá então 2 componentes conexas e com e vértices e e arcos respectivamente.
e são grafos conexos e sem ciclos logo por hipótese de indução:
Tirámos um arco a , mas não tirámos nenhum vértice. O número de vértices de será então:
O número de arestas de é então:
Está provado por indução.