זרימה לא מתאפסת
זרימה לא מתאפסת בגרף מכוון מעל חבורה אבלית היא השמה של אברי החבורה (פרט לאפס) לקשתות של הגרף כך שבכל קודקוד סכום הקשתות היוצאות יהיה שווה לסכום הקשתות הנכנסות. דרישה זאת נקראת לעיתים "חוק קירכהוף". בגרף לא מכוון, נוסף להשמה לקשתות צריך להוסיף אוריינטציה (כיוון) לקשתות. אם קיימת זרימה לא מתאפסת של חבורה מסוימת עם אוריינטציה אחת של הגרף אז קיימת זרימה לא מתאפסת עם אוריינטציה אחרת, מכיוון שחבורה סגורה להופכי. לכן ניתן לדבר על קיום זרימה לא מתאפסת ללא ציון האוריינטציה.
השאלה החשובה בהקשר של זרימה לא מתאפסת היא באיזה גרפים קיימת זרימה לא מתאפסת של חבורה נתונה. לכל חתך של גרף סכום הקשתות מתאפס. לכן בגרף עם גשר (קשת שאם מורידים אותה מספר רכיבי הקשירות גדל) אין זרימה לא מתאפסת מעל כל חבורה. מאידך, בכל גרף ללא גשר (שנקרא 2-קשיר) קיימת זרימה לא מתאפסת, מכיוון שקיימת אוריינטציה של הקשתות שהופכת אותו לקשיר היטב. משפט המפתח שהוכיח ויליאם טאט (Tutte) הוא כי קיום הזרימה תלוי אך ורק בגודל החבורה ולא במבנה שלה וכי אם יש זרימה מעל חבורה מסוימת אז יש זרימה מעל חבורה גדולה יותר. לכן ניתן להגדיר זרימת-k לא מתאפסת של גרף בתור זרימה לא מתאפסת מעל חבורה כלשהי בגודל k.
לגרף יש זרימה-2 לא מתאפסת אם ורק אם הוא אוילרי. טאט שיער ב-1954 כי לכל גרף נטול גשרים יש זרימת-5 לא מתאפסת. ידוע בעקבות עבודותיהם של פרנסואה ז'גר ופול סימור כי כל גרף נטול גשרים יש זרימת-6 לא מתאפסת.
לזרימה לא מתאפסת קשרים הדוקים עם צביעת קודקודים וצביעת קשתות של גרפים. היא נחקרה לראשונה כגישה להוכחת משפט ארבעת הצבעים. ניתן להראות כי לגרף מישורי ללא גשרים שמשוכן במישור יש זרימת-k לא מתאפסת אם ורק אם לגרף הדואלי (המתאים לפנים של הגרף המשוכן) יש צביעה בקודקודים עם k צבעים. בגרף ללא גשרים שלכל קודקודיו דרגה 3 ניתן לצבוע את קשתותיו ב-3 צבעים אם ורק אם יש לו זרימת-3 לא מתאפסת. ניתן לראות זאת על ידי שימוש בחבורת הארבעה של קליין . לכן משפט ארבעת הצבעים שקול לטענה כי כל גרף מישורי ללא גשרים לכל קודקודיו דרגה 3 ניתן לצבוע את קשתותיו עם שלושה צבעים. בעיית ההכרעה האם גרף שדרגתו 3 ניתן לצביעה עם שלושה צבעים היא שלמה לNP (כפי שהראה הולייר [1]) ומכאן שגם שאלת קיום זרימת-3 לא מתאפסת היא NP שלמה.
