My friend Gary challenged me to try to encode a directed graph as an undirected graph. Clearly jealous of my superior intellect, every time I came up with a solution (e.g. “A single node, where the label of the node is the Base64 encoding of the directed graph.”), he’d make up some excuse why my answer was not acceptable (“no labels”, “there’s a million boring ways to solve the problem as originally stated, so I have to make it more interesting”, “what if you wanted this translation to be easy to do by hand?”, etc.).

As an aside, a label-less graph is a mindfuck for me, ’cause a graph is only interesting in that it shows the relationships between the actual payloads, which are the labels. Apparently that makes me a computer scientist, whereas Gary is a mathematician.

Anyway, the solution he finally accepted from me is as follows: Assign each node from the directed graph with a numerical ID, and then represent node N as a clique of size N in the undirected graph. Then in order to represent directed edges, I just had to come up with some sort of assymetric structure with two ends to act like a super-edge.

He posted his own solution on his blog, but I argue that his solution is not easy to perform by hand at all (and not simply because I am too dimwitted to follow along with his solution).

In response, I showed him how easy it was to perform my transformation by hand, by vandalizing his blog post. In that diagram, I assigned node A with ID one billion, and node B with ID two billion.

Gary points out that if I could just bring myself to accept graphs without labels, I could always represent every node with a clique of size 3, instead of a billion.