Изменения

Рассмотрим каркас <tex>T </tex> графа <tex>G</tex>. <tex>e_1,...,e_{s}</tex> — все ребра графа <tex>G </tex> которые не входят в каркас <tex>T</tex>. При добавлении <math>e_{i}</math> образуется простой цикл <tex>C_{i}</tex>. Семейство циклов <tex>C_1 ... C_{s}</tex> называется '''фундаментальными циклами графа <tex>G </tex> относительно каркаса <tex>T</tex>'''

Множество всех фундаментальных циклов относительно любого каркаса <tex>T </tex> графа <tex>G </tex> образует базис циклического пространства этого графа.

Рассмотрим каркас <tex>T </tex> графа <tex>G </tex> и фундаментальные циклы <tex> C_1 ... C_{s} </tex> относительно каркаса <tex>T</tex>. В каждом из <tex> С_{i} </tex> есть ребро <tex>e_{i}</tex> которое принадлежит ровно одному из <tex> C_1 ... C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса <tex>Т </tex> не является пустым графом, из чего следует, что <tex> C_1 ... C_{s} </tex> линейно независимы.Докажем, что любой цикл из циклического пространства графа <tex>G </tex> является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, <tex> e_1 ... e_{k} </tex> ребра принадлежащие <tex>Z </tex> и не принадлежащие <tex>T</tex>. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus ... \oplus C_{k} </tex>. Каждое из ребер <tex> e_{t} , t = 1,..,k </tex> встречается ровно в двух слагаемых — <tex>Z </tex> и <tex>C_{k}</tex>. Значит <tex>F </tex> содержит только ребра из <tex>T</tex>. Так как <tex> C_1 ... C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин <tex>Z </tex> тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин <tex>F </tex> четны. Если <tex>F </tex> непустой граф то в <tex>F </tex> есть цикл, значит цикл есть и в <tex>T</tex>. Значит <tex>F </tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>.