Da musst du dich halt entscheiden.
Was
msdn sagt ist nicht wirklich relevant, wenn ich mir ankucke was MS alles schon für Schrott produziert hat...
Die Lösung mit den Exceptions ist doch gar nicht so schlecht. Wenn es dir auf den Keks geht, dass der Debugger dann immer anhält, kannst du ja in den Debugger-Optionen eine Ausnahme für
EInvalidGraphException hinzufügen.
Ansonsten halt mit Rückgabewerten, allerdings würde ich dann schon einen Enumerationstyp dem einfachen Integer vorziehen.