Le deuxième ensemble de validations structurelles effectuées sont les vérifications de graphe. Elles garantissent que le graphe de flux correspond à un graphe acyclique connecté et dirigé. Ces validations incluent :
- Le flux de travaux doit former un graphe 'connecté'. Cela signifie que chaque activité doit apparaître dans au moins un chemin entre l'activité de début et l'activité de fin.
- Le flux de travaux doit constituer un diagraphe acyclique. Cela signifie qu'aucun chemin via le flux de travaux n'impacte deux fois la même activité. Cette validation n'effectue la vérification que pour les cycles créés par les transitions (les cycles créés avec des activités de début de boucle et de fin de boucle sont parfaitement valides).
- Chaque sous-graphe d'instance dans le graphe de flux de travaux doit se terminer correctement. Cela signifie que tous les chemins possibles dans le flux de travaux, commençant par l'activité de début, doivent se terminer par l'activité de fin.