This may come off as a weird exercise, because I'm talking about a finite amount of edges to be specified, which begs the question: why not just write them down? However, I was asked to use a set-builder notation in order to describe the platonic solids - in my case, I'm using vertices or nodes for their faces, and edges as they are - and I only got four of them right:
tetrahedron = [(j,i) | i <- [1..4], j <- [1..i], i/=j]
cube = [(j,i) | i <- [1..6], j <- [1..i], i/=j, i+j/=7]
octahedron = [(j,i) | i <- [1..8], j <- [1..i], k <- [3,7,9,11,15], i/=j, i+j==k]
dodecahedron = [(j,i) | i <- [1..12], j <- [1..i], k <- [3,4,5,8,12,13,15,16,17,20], i/=j, i+j==k, i-j/=6]
The tetrahedron is the same as the complete graph with 4 vertices, the cube construction generates more edges than necessary, those whose vertices add up to 7 so that I can exclude them, and the octahedron is a case where they must add up to the odd numbers specified. The dodecahedron was difficult, but I figured that I had to create an exception, which was a difference of 6 between the vertices' numbers.
Is it possible to create an icosahedral graph in the same manner? Is there math that says that it's not possible otherwise?
Hamiltonian graphs can be specified in generalized LCF notation. You walk around a Hamiltonian cycle and number the vertices sequentially starting at 0. Each node is obviously adjacent to the node one higher and one lower; the GLCF notation gives the "missing" edges as offsets, together with a number of times you should replicate those offsets. An example of GLCF is [(-4,-3,4),(-2,2,3)]6. This means that the first vertex is attached to vertices 4 behind, 3 behind, and 4 ahead of it on the cycle; the second vertex is attached to vertices 2 behind, 2 ahead, and 3 ahead of it on the cycle; then we repeat that six times total, so the third vertex is again attached 4 behind, 3 behind, 4 ahead; the fourth is attached 2 behind, 2 ahead, 3 ahead; etc. up to the twelfth and final node.
We can turn a GLCF notation into the adjacency list using list comprehension syntax:
glcf :: [[Int]] -> Int -> [(Int, Int)]
glcf offsets repetitions =
[ (k, k')
| i <- [0..repetitions-1]
, (j, os) <- zip [0..] offsets
, let k = i*n+j
, o <- -1:1:os
, let k' = (k+o)`mod`(n*repetitions)
, k<k'
]
where
n = length offsets
In many cases, each node has exactly one missing edge. Then it's customary to drop the parentheses from the tuples of GLCF, and this abbreviated form is called LCF notation. We can make a similar distinction in Haskell:
lcf :: [Int] -> Int -> [(Int, Int)]
lcf = glcf . map return
MathWorld gives GLCF notation for most of the platonic graphs; check out this page for links to descriptions of each of them. Oddly it does not list a version for the octahedron graph. I don't know why, as it is easy to see what it ought to be from staring at its various renderings of the graph. We can import the others directly:
tetrahedron = lcf [-2] 4
cube = lcf [3,-3] 4
octahedron = glcf [[2,-2]] 8
icosahedron = glcf [[-4,-3,4],[-2,2,3]] 6
dodecahedron = lcf [-10,-4,7,-7,4,-10,7,4,-4,-7] 2