Let G be a 3-regular graph without bridges. Show that G has a perfect matching [Pet91]. Does this also hold for 3-regular graphs containing bridges? Does a 3-regular graph without bridges necessarily have a 1-factorization? Let G = (V,E) be a digraph having n vertices, m edges, and p connected components. Let M be the incidence matrix of G, and let q : V → R be a mapping which we call a potential. We define δq : E → R by δq(xy) = q(y) − q(x) forxy ∈ E.