Open Problem Garden

not too hard

On November 25th, 2007 mdevos says:

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:

$G$

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.

Open Problem Garden

not too hard

Reply

Navigate

Recent Activity