Hallo,
ich verstehe das so:
Wir haben den vollständigen bipartiten Graphen \(G=(X \cup Y,E)\), wobei X und Y jeweils 2n Elemente enthalten. Wir such \(n^2\) Teilgraphen \(K_i=(X_i \cup Y_i,E_i)\), die Kreise sind - und zwar so, dass jede Kante aus E in genau einer der Kantenmengen \(E_i\) enthalten ist.
Für n=1 ist der Graph ein Kreis - fertig.
Es sei also jetzt \(G=(X \cup Y,E)\) der vollständige bipartite Graph mit jeweils (2n+2) Elementen, sagen wir mit \(x_1, \ldots,x_{2n},x_{2n+1},x_{2n+2}\), y analog. Dann sei G' der Teilgraph von G mit den Knoten \(x_1, \ldots x_{2n}\), y analog. Dafür gibt es n^2 Kreise nach Induktionsvoraussetzung.
Wir ergänzne diese Kreise durch
$$(\{x_{2i-1},x_{2i},y_{2n+1},y_{2n}\}, E_{1,i}) \text{ mit den benötigten Kanten aus E}, i=1, \dots n$$
$$(\{x_{2n+1},x_{2n},y_{2i-1},y_{2i}\}, E_{2,i}) \text{ mit den benötigten Kanten aus E}, i=1, \dots n$$
$$(\{x_{2n+1},x_{2n},y_{2n+1},y_{22}\}, E_0) \text{ mit den benötigten Kanten aus E}$$
Das sind 2n+1 Stück.
Gruß Mathhilf
