Flow‐Critical Graphs

Abstract

ABSTRACT Lovász et al. proved that every six‐edge‐connected graph has a nowhere‐zero three‐flow. In fact, they proved a more technical statement, which says that there exists a nowhere‐zero three‐flow that extends the flow prescribed on the incident edges of a single vertex with bounded degree. We extend this theorem of Lovász et al. to allow to have an arbitrary degree, but with the additional assumption that there is another vertex with a large degree and no small cut separating and . Using this theorem, we prove two results regarding the generation of minimal graphs with the property that prescribing the edges incident to a vertex with specific flow does not extend to a nowhere‐zero three‐flow. We use this to further strengthen the theorem of Lovász et al., as well as give a density bound on flow‐critical graphs with at most one vertex of degree at least 7.