[Richard Suchenwirth] - As another part of [Graph theory in Tcl], here's a routine that produces a graph description (list of edges like ''x,y'', where x and y are the adjacent vertices) for complete r-partite graphs. You specify the number of partitions (what is written as exponent to K in textbooks) and optionally the size of each partition (conventionally subscript to K, defaults to 1):
 proc graphK {nPartitions {sizeOfPartition 1}} {
    set partitions {}
    set no 0
    for {set i 0} {$i<$nPartitions} {incr i} {
        set partition {}
        for {set j 0} {$j<$sizeOfPartition} {incr j} {
            lappend partition [incr no]
        }
        lappend partitions $partition
    }
    foreach p $partitions {
        foreach p2 $partitions {
            if {$p==$p2} continue
            foreach vertex $p {
                foreach v2 $p2 {
                    if {$vertex>$v2} break
                    lappend res $vertex,$v2
                }
            }
        }
    }
    set res
 }
Now testing with the two minimal non-planar graphs, that cannot be drawn on a flat surface without crossing edges:
 0 % graphK 5   ;# pentagon in a pentagram
 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5
 0 % graphK 2 3 ;# "Gas-Water-Electricity" graph
 1,4 1,5 1,6 2,4 2,5 2,6 3,4 3,5 3,6
What is so different about Tcl that it that I enjoy writing such algorithms at breakfast?
----
[Arts and crafts of Tcl-Tk programming]