Premium
3‐Flows and Combs
Author(s) -
Silva Cândida Nunes,
Lucchesi Cláudio L.
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21785
Subject(s) - mathematics , combinatorics , conjecture , counterexample , graph , connectivity , enhanced data rates for gsm evolution , flow (mathematics) , discrete mathematics , geometry , computer science , telecommunications
Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G ; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.