Доказательство. Пусть — произвольная вершина такого бесконечного графа, и пусть — множество вершин, смежных ,Пусть Следствие Каждый связный локально конечный бесконечный граф является счетным. Помимо этого, на бесконечный граф 1. Конечный маршрут в 2. Бесконечным в одну сторону маршрутом в 3. Бесконечным в обе стороны маршрутом в графе Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются очевидным образом, так же как и понятия длины цепи и расстояния между вершинами. Бесконечные простые цепи не так уж трудно обнаружить. Теорема 6.1. (Кениг, 1936) Пусть
|
— произвольная вершина такого бесконечного графа, и пусть 
— множество вершин, смежных 
— множество всех вершин, смежных вершинам из 
тоже счетны. Здесь используется тот факт, что объединение не более чем счетного множества счетных множеств счетно. Следовательно, 
— последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат.
можно перенести понятие маршрута, причем тремя различными способами:
, 
. Маршрут можно обозначить и так: 
.
называется бесконечная последовательность ребер вида 
.
, 
