El producto cartesiano de dos gráficas se utiliza para comparar rutas entre éstas, si hacemos el producto cartesiano de una gráfica consigo misma lo que obtendremos son las distintas rutas que existen para recorrer un mismo camino en un diagrama. Esta es la idea que hay detrás del diagrama de parejas, utilizado como herramienta básica en el estudio de autómatas en general [McIntosh 91a], en este caso el diagrama de de Bruijn se utilizará como base para generar al diagrama de parejas.
Cada nodo del diagrama de parejas es una posible dupla de nodos del diagrama de de Bruijn, de este modo el diagrama de parejas tendrá tantos nodos como 
; las ligas en este diagrama partirán de un nodo a otro si el primer elemento del nodo inicial con el primer elemento del nodo final tiene el mismo color de liga en el diagrama de de Bruijn que el segundo elemento del nodo inicial con el segundo elemento del nodo final.
Debido a esta construcción, las rutas del diagrama de parejas corresponden a parejas de rutas iguales del diagrama de de Bruijn, este diagrama esta contenido tal cual en la diagonal principal del diagrama de parejas.