Изменения

* <tex> {{Лемма|Vid = lem1| about = n^l </tex>. Очевидно из определения <tex> V </tex>.об эйлеровости графа* |statement= Граф де Брюина <tex> l = 1 \Leftrightarrow G - </tex> полный граф. эйлеровДействительно, для любых (необязательно различных) вершин <tex> u, v \ \exists L |proof= \alpha \beta </tex>Ориентированный граф является эйлеровым, где <tex> \alpha, \beta - </tex> слова (символы), соответствующие вершинам <tex> u, v </tex>если число входящих рёбер равно числу исходящих. И тогда очевидноДокажем, что существует ребро это верно для <tex> e = B(un, vl)\ \forall u, v \in V </tex>.* А именно, что <tex> \forall v \in V </tex> верно, что <tex> deg_{out}(v) = n = deg_{in}(v)</tex>. Докажем первое равенство, второе аналогично. Существует ровно <tex> n </tex> символов алфавита, которые можно добавить в конец слова <tex> \alpha</tex>, соответствующему вершине <tex> v </tex>. Получим ровно <tex> n </tex> различных слов. И у всех этих слов различные суффиксы длины <tex> l </tex>. Таким образом, из вершины <tex> v </tex> выходит ровно <tex> n </tex> рёбер и входит тоже <tex> n </tex> рёбер.* Значит, граф де Брюина <tex> G - </tex> эйлеров. Это следует }} {{Лемма|id = lem2|about = о количестве вершин и рёбер в графе|statement= В графе де Брюина <tex> B(n, l): |V| = n^l, |E| = n^{l+1}</tex>|proof= Число вершин очевидно находится из предыдущего свойства, так как число входящих определения графа и исходящих равно <tex> n^l </tex>. Число рёбер равныследует из доказательства предыдущей леммы: каждой вершине инцидентно ровно 2 ребра.Таким образом, <tex> |E| = \frac{1}{2} \cdot n^l \cdot 2n = n^{l+1} </tex> }} {{Лемма|id = lem3|about = о равносильном определении* |statement= В графе де Брюина <tex> B(n, l): e = (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>. |proof= <tex> \Leftarrow </tex>