El segundo conjunto de validaciones estructurales que se llevan a cabo son las comprobaciones de grafo. Estas garantizan que el grafo del flujo sea un grafo dirigido, conectado y acíclico. Dichas validaciones incluyen:
- El flujo de trabajo deberá formar un grafo 'conectado'. Esto significa que cada actividad deberá aparecer en al menos una ruta que vaya de la actividad de inicio a la actividad de finalización.
- El flujo de trabajo deberá formar un dígrafo acíclico. Esto significa que no puede haber ninguna ruta en el flujo de trabajo que pase dos veces por la misma actividad. Esta validación se aplica a ciclos creados solo por las transiciones - los ciclos creados mediante actividades de inicio y fin de bucle (loop-begin-activity y loop-end-activity respectivamente) son perfectamente válidos.
- Cada subgrafo de instancia dentro del flujo de trabajo deberá terminar correctamente. Esto significa que, comenzando en la actividad de inicio, toda ruta posible en el flujo de trabajo deberá terminar en la actividad de finalización.