not too hard

I believe that this conjecture is true, and that it can be proved with standard tools. I will sketch the argument here. I certainly wouldn't claim this is a particularly great proof.. it's just the one my nose lead me to first. The main tools I need are as follows.

Theorem  (Tutte)   If $ G $ does not have a perfect matching, then there exists a subset of vertices $ Y $ so that $ G \setminus Y $ has more than $ |Y| $ components which have an odd number of vertices.
Corollary   If $ G $ is a connected bridgeless cubic graph, then for every edge $ e $, there exist perfect matchings $ M,M' $ so that $ e \in M $ and $ e \not\in M' $.

Now, let $ G $ be a connected bridgeless cubic graph with the property that every 2-factor of $ G $ is a (disjoint) union of cycles of length 5. Using the corollary (carefully), you can show the following in order:

    \item $ G $ does not have a cycle of length 2. \item $ G $ does not have two triangles which share an edge. \item $ G $ does not have a square and a triangle which share an edge. \item $ G $ does not have a triangle. \item $ G $ does not have a square.

Thus, $ G $ must have girth 5. Next we will show that $ G $ is 3-edge connected using the same corollary. Suppose (for a contradiction) that $ G $ is only 2-edge-connected, and let $ u v, u'v' $ be two edges which form a 2-edge cut so that $ u $ and $ u' $ are in the same component of $ G \setminus \{uv, u'v'\} $. Now, there must exist a perfect matching not using $ uv $, so the complementary 2-factor must contain a 5-cycle which uses both the edges $ uv $ and $ u'v' $. It follows that either $ uu' $ is an edge or $ vv' $ is an edge, and we may assume the latter without loss. Let $ w $ be the neighbor of $ v $ other than $ u,v' $ and let $ w' $ be the neighbor of $ v' $ other than $ u',v $. Now, there exists a perfect matching containing the edge $ vv' $, and the complementary 2-factor must contain a 5-cycle which uses all of the edges $ uv, vw, u'v', v'w' $. It follows that either $ u=u' $ or $ w = w' $, but either of these contradicts the fact that $ G $ is bridgeless. This contradiction shows that $ G $ is 3-edge connected. By a similar argument, you can prove that every 3-edge cut of $ G $ consists of 3 edges incident with a common vertex. So, $ G $ is cyclically 4-edge connected.

Next we establish that $ G $ has property (*) which is a strengthening of what appears in the corollary.

(*) If $ u,v,w,x \in V(G) $ and $ uv,vw,wx \in E(G) $, then there is a perfect matching containing both $ uv $ and $ wx $.

Suppose (for a contradiction) that (*) does not hold. Then $ G' = G \setminus \{u,v,w,x\} $ has no perfect matching, so by Tutte's theorem there exists a subset of vertices $ Y \subseteq V(G') $ so that $ G' \setminus Y $ has more than $ |Y| $ odd components. Let $ {\mathcal I} $ be the set of isolated vertices in $ G' \setminus Y $, let $ {\mathcal O} $ be the set of odd components of $ G' \setminus Y $ with size $ >1 $, and let $ {\mathcal E} $ be the set of even components of $ G' \setminus Y $. We know that $ |Y| < |{\mathcal I}| + |{\mathcal O}| $ by assumption, but in fact $ |Y| + 2 \le |{\mathcal I}| + |{\mathcal O}| $ since $ |Y| - |{\mathcal I}| - |{\mathcal O}| $ must be an even number (as $ |V(G')| $ is even). Now, let $ Y^+ = Y \cup \{u,v,w,x\} $ and let $ C $ be the edge cut in $ G $ which separates $ Y^+ $ from the rest of the vertices ($ V(G) \setminus Y^+ $). It follows from our construction that $ |C| \le 3|Y| + 6 $ since every vertex in $ Y $ can contribute at most 3 edges to $ C $, and there are at most 6 edges in $ C $ with one of $ u,v,w,x $ as endpoint. On the other hand, since $ G $ is cyclically 4-edge connected, every component in $ {\mathcal O} \cup {\mathcal E} $ must contribute at least 4 edges to $ C $, and every vertex in $ {\mathcal I} $ contributes exactly 3 edges to $ C $, so $ |C| \ge 3|{\mathcal I}| + 4|{\mathcal O}| + 4 |{\mathcal E}| \ge 3( |Y| + 2 ) + |{\mathcal O}| + 4|{\mathcal E}| $. It follows from this that $ {\mathcal O} = \emptyset = {\mathcal E} $, and that every vertex in $ Y $ must have all three incident edges in $ C $. Thus, $ G \setminus \{uv, vw, wx\} $ is a bipartite graph. Now, there exists a perfect matching of $ G $ which contains the edge $ uv $, and every odd cycle in the complementary 2-factor must contain either $ vw $ or $ wx $, so the complementary 2-factor cannot have 2 odd cycles - giving us a contradiction.

With property (*) in hand, we are ready to complete the proof. Property (*) implies that every 3-edge path must be contained in a cycle of length 5, and it follows from this that every 2-edge path of $ G $ is contained in at least two 5-cycles. Let $ u $ be a vertex of $ G $, let $ v,w,x $ be the neighbors of $ u $, and assume that the neighbors of $ v,w,x $ are $ \{u,v_1,v_2\} $, $ \{u,w_1,w_2\} $, and $ \{u,x_1,x_2\} $ (respectively). It follows from the fact that $ G $ has girth 5 that all of these vertices we have named are distinct. Since the 2-edge path with edges $ vu,uw $ is contained in two cycles of length 5, there must be $ \ge 2 $ edges between $ \{v_1,v_2\} $ and $ \{w_1,w_2\} $. Similarly, there are $ \ge 2 $ edges between $ \{w_1,w_2\} $ and $ \{x_1,x_2\} $, and between $ \{x_1,x_2\} $ and $ \{v_1,v_2\} $. It follows from this that $ V(G) = \{u,v,w,x,v_1,v_2,w_1,w_2,x_1,x_2\} $, and with a little more work using the girth assumption, it can be shown that $ G $ is isomorphic to Petersen as required.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options