Abstract
An edge of a matching covered graph \(G\) is a forcing edge if it lies in precisely one perfect matching of \(G\). A matching covered graph is a brick if and only if it is 3-connected and bicritical (the deletion of each pair of distinct vertices results in a graph with a perfect matching). In this paper, we prove that every vertex of a brick is incident with a forcing edge if and only if the brick is an odd wheel up to multiple edges.
Keywords: Bricks; Solid bricks; Perfect matchings; Forcing edges
1 Introduction↩︎
All graphs considered here are finite and loopless; multiple edges are allowed unless otherwise stated. The underlying simple graph of \(G\) is the simple graph obtained from \(G\) by deleting all but one of the edges joining each pair of adjacent vertices. For the terminology that is specific to matching covered graphs, we follow Lovász and Plummer [1]. A perfect matching is a set of edges incident with every vertex exactly once. A graph is matchable if it has a perfect matching. A connected graph with at least one edge is matching covered if each edge belongs to some perfect matching. A graph \(G\) is bicritical if it contains at least four vertices, and \(G-u-v\) is matchable for each pair of distinct vertices \(u\) and \(v\) of \(G\). For a nonempty proper subset \(X\) of \(V(G)\), the edge set \(\partial_G(X)=\{xy\in E(G): x\in X,\;y\in V(G)\setminus X\}\) is called an edge cut of \(G\). The vertex sets \(X\) and \(\overline{X}\) are called the shores of the edge cut \(\partial_G(X)\), where \(\overline{X} = V(G) \setminus X\). The edge cut \(\partial_G(X)\) is trivial if one of its shores has exactly one vertex, and it is tight in a matching covered graph if every perfect matching meets it in exactly one edge. A nonbipartite matching covered graph without nontrivial tight cut is called a brick. Equivalently, by the theorem of Edmonds, Lovász and Pulleyblank [1], bricks are 3-connected bicritical graphs. Bricks are the nonbipartite atoms in the tight cut decomposition of matching covered graphs, a theory developed by Kotzig, Lovász, Plummer and others; see the monographs of Lovász and Plummer [1] and Lucchesi and Murty [2]. A central result is Lovász’s theorem [3], which states that any two tight cut decompositions of a matching covered graph yield the same list of bricks and braces, up to multiple edges.
For a graph \(G\) with a perfect matching, an edge \(uv\) of \(G\) is called a forcing edge (also known as solitary in [2]) if \(G-u-v\) has a unique perfect matching; equivalently, \(uv\) is contained in exactly one perfect matching of \(G\). The idea arose in chemical graph theory in connection with Kekulé structures, first through the innate degree of freedom of Klein and Randić [4] and later through the terminology of forcing used by Harary, Klein and Živković [5]; see also Adams, Mahdian and Mahmoodian [6] and the survey [7]. Forcing edges also occur in the study of uniquely forced perfect matchings in cubic and highly connected graphs [8], [9]. Recently, Goedgebeur et al. [10] studied forcing edges in bridgeless cubic graphs. They reduced the problem to the corresponding class of \(3\)-connected cubic graphs and proved that every graph in this class has at most six forcing edges. It is easy to check that a forcing edge \(e\) of a matching covered graph \(G\) remains forcing in any brick \(H\) obtained from a tight cut decomposition of \(G\), provided that \(e\in E(H)\). With the help of forcing edges, de Carvalho, Lucchesi and Murty [11] present a characterization of extremal bricks. Motivated by these results, we consider a vertex version of forcing edge conditions in bricks. More precisely, we study bricks with the following property \(\mathcal{P}\): every vertex is incident with at least one forcing edge.
A wheel is obtained from a cycle, called the rim, by adding a new vertex, called the hub, adjacent to every vertex of the rim. The vertices and edges of the rim are called rim vertices and rim edges, and the edges joining the hub to the rim vertices are called spokes. The wheel is odd if its rim has odd length. It can be checked that in an odd wheel every spoke is a forcing edge, and hence the odd wheel has property \(\mathcal{P}\). Furthermore, we show the following.
Theorem 1. Let \(G\) be a simple brick. Then \(G\) has property \(\mathcal{P}\) if and only if \(G\) is an odd wheel.
Our main result shows that, among bricks (allowing multiple edges), odd wheels with possible multiple edges on spokes are the only graphs satisfying property \(\mathcal{P}\); see the note below for the precise distribution of multiple edges.
Note 2. If the graph \(G\) in Theorem 1 is allowed to be a brick with multiple edges, then the hypothesis still implies that the underlying simple graph of \(G\) is an odd wheel. In particular, if \(|V(G)|=4\), then the edges of multiplicity one must consist of either two nonadjacent edges or a triangle; and if \(|V(G)|\geq 6\), then every multiple edge of \(G\) must be a spoke.
The proof of Theorem 1 uses the distinction between solid and nonsolid bricks. In the solid case, a forcing edge gives strong restrictions on the neighbors of its two incident vertices. Repeating this local argument throughout the graph forces the whole brick to have the structure of an odd wheel.
In the nonsolid case, robust cuts are used to decompose a hypothetical nonsolid counterexample. The resulting solid pieces are odd wheels up to multiple edges, but splicing two such pieces always leaves some vertex outside property \(\mathcal{P}\).
2 Preliminaries↩︎
The degree of a vertex \(v\) in \(G\), denoted by \(d_G(v)\), is the number of edges of \(G\) incident with \(v\). For a vertex \(u\), let \(\partial_G(u)\) be the set of edges incident with \(u\) and let \(N_G(u)\) be the set of neighbors of \(u\), and \(d_G(u)=|\partial_G(u)|\). For any \(x, y \in V(G)\), a path from \(x\) to \(y\) is called an \(x\)-\(y\) path. For a graph \(G\) with a matching \(M\), a path is called an \(M\)-alternating path if its edges alternate between \(M\) and \(E(G)\setminus M\). A vertex of degree \(k\) is also called a \(k\)-degree vertex. For a set \(S\subseteq V(G)\), \(G[S]\) denotes the subgraph induced by \(S\). If \(X\) is contracted to a single vertex \(x\), the resulting graph is denoted by \(G/(X\to x)\), or simply by \(G/X\) when the label of the contracted vertex is irrelevant.
2.1 Cuts and Splicing↩︎
We shall use the following splicing operation. Let \(G\) and \(H\) be vertex disjoint graphs, and let \(u\in V(G)\) and \(v\in V(H)\) satisfy \(d_G(u)=d_H(v)\). Given a bijection \(\theta:\partial_H(v)\to \partial_G(u)\), the graph obtained by splicing \(G\) at \(u\) with \(H\) at \(v\), denoted by \((G(u)\odot H(v))_\theta\), is obtained from \(G-u\) and \(H-v\) by joining, for each edge \(vw\in \partial_H(v)\), the vertex \(w\) to the other end of \(\theta(vw)\) in \(G\). The set of these new edges is called the splicing cut. When the vertices and bijection are clear, we simply write \(G(u)\odot H(v)\).
The two graphs obtained from \(G\) by contracting each shore of an edge cut \(C\) separately to a single vertex are called the \(C\)-contractions of \(G\). An edge cut \(\partial_G(X)\) in a matching covered graph \(G\) is a separating cut if both graphs obtained from \(G\) by contracting \(X\) and \(\overline{X}\), respectively, are matching covered. A near-brick is a matching covered graph with a single brick, and a separating cut \(C\) of a brick \(G\) is a robust cut if both \(C\)-contractions of \(G\) are near-bricks. If \(S\subseteq V(G)\) and \(F\subseteq E(G)\), we say that \(S\) covers \(F\) if every edge of \(F\) has an end in \(S\).
Theorem 3. [11], [12] Every nonsolid brick \(G\) has a robust cut \(\partial(X)\) such that there exists a subset \(X'\) of \(X\) and a subset \(X''\) of \(\overline{X}\) such that \(G / \overline{X'}\) is a solid brick, \(G / \overline{X''}\) is a brick, and the graph \(H\), obtained from \(G\) by contracting \(X'\) and \(X''\) to single vertices \(x'\) and \(x''\), respectively, is bipartite and matching covered, where \(x'\) and \(x''\) lie in different color classes of \(H\).
Lemma 4. [1] If a bipartite nontrivial graph \(H := H[A, B]\) has a unique perfect matching, then at least one vertex in \(A\), and at least one in \(B\), have degree one.
Lemma 5. Assume that \(\partial(X_i)\) is an edge cut of a brick \(G\) such that \(G_i = G/\overline{X_i}\) is a brick, for \(i \in \{1, 2\}\), and \((G/(X_1 \to x_1))/(X_2 \to x_2)\) is a matching covered bipartite graph \(H\). If \(|V(H)| \ge 4\), then every edge of \(E(H) \setminus E_H(x_1, x_2)\) is not forcing in \(H\).
Proof. Assume that \(A\) and \(B\) are the two color classes of \(H\). Let \(uv \in E(H) \setminus E_H(x_1, x_2)\) with \(u\in A\) and \(v\in B\). Suppose, to the contrary, that \(uv\) is forcing in \(H\). Then \(H-u-v\) has a unique perfect matching. By Lemma 4, there are vertices \(a\in A\setminus\{u\}\) and \(b\in B\setminus\{v\}\) such that both \(a\) and \(b\) have degree one in \(H-u-v\). Since \(H\) is bipartite and matching covered with \(|V(H)|\ge 4\), every vertex of \(H\) has at least two distinct neighbors. Thus each of \(a\) and \(b\) has exactly two neighbors in \(H\). Since \(G\) is 3-connected, each of \(a\) and \(b\) has at least three neighbors in \(G\). It implies that at least one of contraction vertex is a neighbor of \(a\) (resp. \(b\)) in \(H\), and the contraction vertex must be joined to \(a\) (resp. \(b\)) by multiple edges. Recall that \(d_{H-u-v}(a)=d_{H-u-v}(b)=1\). For the graph \(H\), \(v\) (resp. \(u\)) is the unique neighbor of \(a\) (resp. \(b\)) incident with multiple edges. Therefore, \(\{u,v\}=\{x_1,x_2\}\), contradicting the fact that \(uv\in E(H)\setminus E_H(x_1,x_2)\). So no edge in \(E(H) \setminus E_H(x_1, x_2)\) is a forcing edge of \(H\). ◻
Lemma 6. [11] For \(i=1,2\), let \(G_i\) be a brick, let \(x_i\in V(G_i)\), and let \(G=(G_1(x_1)\odot G_2(x_2))_{\theta}\). Then \(G\) is a brick if and only if no pair of vertices of \(G\), one in \(V(G_1)\setminus\{x_1\}\) and the other in \(V(G_2)\setminus\{x_2\}\), covers the set of edges in \(\partial_G(V(G_1)\setminus\{x_1\})\).
The following result follows directly from the definition of forcing edges.
Proposition 7. Let \(G_1\) and \(G_2\) be matching covered graphs, and let \(G=(G_1(u)\odot G_2(v))_{\theta}\). Denote the corresponding splicing cut by \(C\).
(i) Let \(e\in E(G_1-u)\), \(M_1\) be a perfect matching of \(G_1\) containing \(e\), \(M_1\cap\partial_{G_1}(u)=\{ua\}\), \(\theta^{-1}(ua)=vb\). Then \(e\) is a forcing edge of \(G\) if and only if \(e\) and \(vb\) are forcing edges of \(G_1\) and \(G_2\), respectively, and every perfect matching of \(G\) containing \(e\) meets \(C\) at exactly one edge (i.e., \(ab\)).
(ii) \(ab\in C\) is a forcing edge of \(G\) with \(a\in V(G_1)\setminus \{u\}\) and \(b\in V(G_2)\setminus \{v\}\) if and only if \(ua\) and \(vb\) are forcing edges of \(G_1\) and \(G_2\), respectively, and every perfect matching of \(G\) containing \(ab\) meets \(C\) at exactly one edge (i.e., \(ab\)).
2.2 Solid Bricks and Forcing Edges↩︎
A brick is solid if its separating cuts are trivial. A graph \(G\) has odd cycle property if for any two vertex disjoint odd cycles \(C_1\) and \(C_2\) of \(G\), the graph \(G-V(C_1)-V(C_2)\) has no perfect matching.
The odd cycle property is inherited by subgraphs whose complements have perfect matchings.
Lemma 9. Let \(G\) be a graph with odd cycle property. If \(H\) is a subgraph of \(G\) such that \(G-V(H)\) has a perfect matching, then \(H\) has odd cycle property.
Proof. Suppose that \(H\) contains two vertex disjoint odd cycles \(C_1\) and \(C_2\) such that \(H-V(C_1)-V(C_2)\) has a perfect matching \(M_H\). Let \(M_0\) be a perfect matching of \(G-V(H)\). Then \(M_H\cup M_0\) is a perfect matching of \(G-V(C_1)-V(C_2)\), contradicting the hypothesis on \(G\). ◻
The next two results mainly concern the existence of 1-degree vertices; this fact will be crucial in the proof of the main structural conclusion.
Lemma 10. [14] Let \(G\) be a graph with a unique perfect matching. If \(G\) has odd cycle property, then \(G\) contains a 1-degree vertex.
Lemma 11. Let \(uv\) be a forcing edge of a solid brick \(G\). Then \(G-u-v\) has at least two 1-degree vertices, which are adjacent to both \(u\) and \(v\).
Proof. Set \(H=G-u-v\). Since \(uv\) is forcing, \(H\) has a unique perfect matching \(M\). By Lemma 8, \(G\) has odd cycle property. By Lemma 9, \(H\) satisfies the hypothesis of Lemma 10; hence \(H\) has a 1-degree vertex \(x\). As \(G\) is a brick, it is 3-connected. So \(x\) is adjacent to both \(u\) and \(v\) in \(G\).
Suppose that \(x\) is the only 1-degree vertex of \(H\). Let \(P\) be a maximal \(M\)-alternating path in \(H\) starting with the unique edge of \(M\) incident with \(x\). Then \(P\) ends with an edge of \(M\); let \(y\) be the end of \(P\), other than \(x\). Since \(y\) is not a 1-degree vertex in \(H\), the maximality of \(P\) implies that the end of each edge in \(\partial(y)\setminus M\) other than \(y\), lies on \(P\). Note that each edge in \(\partial(y)\setminus M\) together with edges in \(P\) cannot form any even \(M\)-alternating cycles, because \(M\) is the unique perfect matching of \(H\); let \(e\in\partial(y)\setminus M\) such that \(e\) forms some odd cycle \(C_2\) with a subpath of \(P\) and the triangle \(C_1=xuvx\) is disjoint from \(C_2\). Therefore, \(G-V(C_1)-V(C_2)\) has a perfect matching \((M \setminus E(P))\cup ((E(P)\setminus E(C_2))\setminus M)\), contradicting Lemma 8. Therefore \(H\) has a 1-degree vertex other than \(x\), say \(z\). Again, by the 3-connectedness of \(G\), \(z\) is adjacent to both \(u\) and \(v\). ◻
The following observation follows directly from Lemma 11.
Corollary 12. Let \(G\) be a solid brick, and let \(ux\) be a forcing edge with \(d_G(x)=3\) and \(N_G(x)=\{u,x^-,x^+\}\). Then \(d_G(x^-)=d_G(x^+)=3\), \(\{ux^-,ux^+\}\subseteq E(G)\), and \(x^-\) and \(x^+\) are the only 1-degree vertices in \(G-u-x\).
2.3 Odd Wheels↩︎
We first study how forcing edges restrict the structure of solid bricks. Then we study how splicing affects property \(\mathcal{P}\). Next, we prove two lemmas.
Lemma 13. Let \(G\) be a simple solid brick. If at most one vertex of \(G\) is not incident with a forcing edge, then \(G\) is an odd wheel.
Proof. If there exists a vertex that is not incident with any forcing edge, denote the vertex by \(z\). Choose a forcing edge \(e=uv\) of \(G\), where \(\{u,v\}\subseteq V(G)\setminus \{z\}\). By Lemma 11, \(G-u-v\) has two vertices of degree one, say \(x_1\) and \(y_1\), and each is adjacent to both \(u\) and \(v\). Thus \(d_G(x_1)=d_G(y_1)=3\).
At least one of \(x_1\) and \(y_1\) is not the exceptional vertex \(z\); without loss of generality, assume that \(x_1\neq z\). Let \(h_1\) be a forcing edge incident with \(x_1\), and let \(x_2\in N_G(x_1)\setminus \{u,v\}\) and \(y_2\in N_G(y_1)\setminus\{u,v\}\). If \(x_2 = y_1\), then \(x_1=y_2\). Hence the edge \(x_1y_1\) forms a component of \(G-u-v\). Since \(G\) is 3-connected, \(G-u-v\) is connected. If there is a vertex other than \(x_1\) and \(y_1\) in \(G-u-v\), then it would be adjacent to \(x_1\) or \(y_1\), contradicting that \(N_G(x_1)=\{u,v,y_1\}\) and \(N_G(y_1)=\{u,v,x_1\}\). Therefore \(V(G)=\{u,v,x_1,y_1\}\) and \(|V(G)|=4\). Since \(G\) is a brick, \(G\cong K_4\).
Next assume that \(x_2 \neq y_1\). If \(h_1=x_1x_2\), then, applying Corollary 12 to the forcing edge \(x_1x_2\), we obtain \(d_G(u)=d_G(v)=3\) and \(\{x_2u,x_2v\}\subseteq E(G)\). However, \(x_2,x_1,v\) and \(y_1\) are four distinct neighbors of \(u\), contradicting \(d_G(u)=3\). So \(h_1=ux_1\) or \(h_1=vx_1\). By the symmetry of \(u\) and \(v\), assume that \(h_1=ux_1\).
Applying Corollary 12 to the forcing edge \(ux_1\), the vertices \(v\) and \(x_2\) have degree three and are adjacent to \(u\). We now extend the path from \(x_1\) through \(x_2\) as follows. Suppose that \(x_i\) has already been chosen, where \(i\geq 2\), and let \(N_G(x_i)=\{u,x_{i-1},x_{i+1}\}\). If \(x_i\neq z\), then \(x_i\) is incident with a forcing edge. This forcing edge cannot be \(x_{i-1}x_i\) or \(x_ix_{i+1}\), for otherwise Corollary 12 would imply \(d_G(u)=3\), while \(u\) is adjacent to the four distinct vertices \(v,x_1,y_1\) and \(x_2\), a contradiction. Hence \(ux_i\) is a forcing edge. Applying Corollary 12 again, we obtain that \(x_{i+1}\) has degree three and is adjacent to \(u\).
Continuing this process, we obtain a maximal sequence \(x_1,x_2,\ldots,x_t\) such that \(ux_i\) is a forcing edge and \(d_G(x_i)=3\) for \(1\leq i<t\), \(x_ix_{i+1}\in E(G)\) for \(1\leq i<t\), and each \(x_i\) is adjacent to \(u\). If \(x_t\neq z\), then \(ux_t\) is also a forcing edge and \(d_G(x_t)=3\). If \(x_t=z\), then \(d_G(z)=3\) and \(uz\in E(G)\) by Corollary 12 applied to the forcing edge \(ux_{t-1}\). By maximality, the sequence stops only when the next vertex already belongs to \(\{v,x_1,\ldots,x_t\}\), or when the exceptional vertex \(z\) exists and \(x_t=z\).
If the sequence closes before reaching \(z\) (or if no such vertex \(z\) exists), then the closed sequence gives a cycle; in particular, when it stops at \(v\) (i.e., \(x_t=y_1\)), the cycle is \(vx_1x_2\cdots x_t v\) and, together with the vertex \(u\), forms a wheel. Since every rim vertex has degree three, every neighbor of a rim vertex lies in the wheel. As \(G\) is 3-connected, this wheel is the whole graph. Thus \(G\) is a wheel. Since a brick has an even number of vertices, the rim has odd length, and so \(G\) is an odd wheel, see Figure 1 (a).
It remains to consider the case in which the sequence reaches \(z\), i.e., \(x_t=z\). If \(y_1=z\), then \(vx_1x_2\cdots x_t v\) is a rim with hub \(u\), and the same argument as in the previous paragraph shows that \(G\) is an odd wheel. Thus assume that \(y_1\neq z\). Repeating the preceding construction starting from \(y_1\), we obtain a maximal sequence \(y_1,y_2,\ldots,y_s\) of 3-degree vertices adjacent to \(u\). If this sequence stops at \(v\), then we again obtain a wheel with hub \(u\). Otherwise it reaches \(z\), and \(vx_1x_2\cdots x_t y_{s-1}\cdots y_2y_1v\) is a rim with hub \(u\), where \(y_s=z=x_t\), see Figure 1 (b). As above, all rim vertices have degree three, so this wheel is the whole graph. Since \(G\) has even order, the rim has odd length. Therefore \(G\) is an odd wheel. ◻
Note 14. If the graph \(G\) in Lemma 13 is allowed to be a solid brick with multiple edges, then the hypothesis still implies that the underlying simple graph of \(G\) is an odd wheel. In particular, if \(|V(G)|=4\), then at least two edges of \(G\) are not multiple edges; and if \(|V(G)|\geq 6\), then every multiple edge of \(G\) must be a spoke.
Lemma 15. Let \(G_1\) and \(G_2\) be two odd wheels up to multiple edges, and let \(G\) be a brick isomorphic to a splicing of \(G_1\) and \(G_2\). Then \(G\) does not have property \(\mathcal{P}\).
Proof. Let \(C\) be the splicing cut. Write the underlying odd wheel of \(G_i\) with hub \(c_i\) and odd rim \(R_i\) for \(i=1,2\). Suppose, to the contrary, that every vertex of \(G\) is incident with a forcing edge. We consider three cases to complete the proof.
Case 1. The two hubs are the splicing vertices.
Let \(C_f=\{e\in C: e \text{ is a forcing edge of } G\}\) and \(\overline{C}_f=C\setminus C_f\). By Proposition 7 (i), no rim edge of either odd wheel is a forcing edge of \(G\). Since every rim vertex is incident with at least one forcing edge of \(G\), such forcing edge must belong to \(C_f\). Set \(G'=G-\overline{C}_f\). We first show that \(G'\) is not a brick.
Suppose that \(G'\) is a brick. The edge set \(C_f\) is a nontrivial cut of \(G'\), and hence it is not tight. Since both shores of \(C_f\) have odd orders, every perfect matching of \(G'\) meets \(C_f\) in an odd number of edges. Therefore there exists a perfect matching \(M_c\) of \(G'\) such that \(|M_c\cap C_f|\geq 3\).
For any \(e\in M_c\cap C_f\), it is not a forcing edge of \(G'\) by Proposition 7 (ii). Naturally \(e\) is not a forcing edge of \(G\), contradicting that \(e\in C_f\). Hence \(G'\) is not a brick.
In this case \(G'\) is obtained from the two odd wheels by splicing them with splicing cut \(C_f\). Applying Lemma 6 to this splicing, there are rim vertices \(x_1\in V(R_1)\) and \(x_2\in V(R_2)\) such that \(\{x_1,x_2\}\) covers \(C_f\). If every edge of \(\overline{C}_f\) is incident with \(x_1\) or \(x_2\), then \(\{x_1,x_2\}\) covers \(C\), and \(G-\{x_1,x_2\}\) is disconnected. This contradicts the 3-connectedness of \(G\). Hence \(\overline{C}_f\) contains an edge \(uv\) with \(u\in V(R_1)\setminus\{x_1\}\) and \(v\in V(R_2)\setminus\{x_2\}\), see Figure 2 (a).
On the odd cycle \(R_1\), the vertices \(x_1\) and \(u\) determine two \(x_1\)-\(u\) paths: one is of odd order and the other is of even order. Let \(P_1\) be the odd one, and let \(y_1\) be the neighbor of \(x_1\) on \(P_1\). Then \(y_1\neq x_1\). So the edge of \(C_f\) incident with \(y_1\) must be \(y_1x_2\). Similarly, on \(R_2\), let \(P_2\) be the odd \(x_2\)-\(v\) path and let \(y_2\) be the neighbor of \(x_2\) on \(P_2\). Then \(x_1y_2\in C_f\).
After deleting all vertices of \(uv\), \(y_1x_2\) and \(x_1y_2\), each rim is split into disjoint paths of even order, and these paths have perfect matchings. Thus \(G\) has a perfect matching \(M_G\) containing \(\{uv,y_1x_2,x_1y_2\}\) such that \(|M_G\cap C|=3\). By Proposition 7 (ii), none of \(\{uv,y_1x_2,x_1y_2\}\) is a forcing edge of \(G\), contradicting that \(x_1y_2\in C_f\).
Case 2. The two splicing vertices lie on rims, respectively.
Let \(x_i\in V(R_i)\) be the splicing vertex of \(G_i\) for \(i=1,2\), and write \(N_{G_i}(x_i)=\{c_i,x_i^-,x_i^+\}\), where \(x_i^-\) and \(x_i^+\) are the two neighbors of \(x_i\) on the rim.
By Proposition 7 (i), the rim edge incident with \(x_1^\varepsilon\) is not forcing in \(G\), where \(\varepsilon\in\{-,+\}\). The edge of \(C\) incident with \(x_1^\varepsilon\) corresponds to the rim edge \(x_1x_1^\varepsilon\) of \(G_1\), and hence is not a forcing edge of \(G\) by Proposition 7 (ii). Since \(x_1^\varepsilon\) is incident with at least one forcing edge of \(G\), such forcing edge must be \(c_1x_1^\varepsilon\). Thus \(|\partial_G(x_1^\varepsilon)\cap C|=1\).
In the odd wheel \(G_1\), the unique perfect matching containing \(c_1x_1^-\) includes the edge \(x_1x_1^+\), and the unique perfect matching containing \(c_1x_1^+\) includes the edge \(x_1x_1^-\). By Proposition 7 (i), the edges of \(G_2\) corresponding to \(x_1x_1^+\) and \(x_1x_1^-\) are forcing edges of \(G_2\). Since every forcing edge of an odd wheel up to multiple edges is a spoke, the two edges of \(C\) incident with \(x_1^-\) and \(x_1^+\) are incident with \(c_2\). The remaining edge of \(C\) is incident with \(c_1\). Hence \(C\subseteq \partial_G(c_1)\cup \partial_G(c_2)\), see Figure 2 (b). Then \(G-\{c_1,c_2\}\) is disconnected, contradicting the 3-connectedness of the brick \(G\).
Case 3. Exactly one splicing vertex lies on a rim.
By symmetry, let \(x_1\in V(R_1)\) be the splicing vertex of \(G_1\), and let the hub \(c_2\) be the splicing vertex of \(G_2\). Let \(x_1^-\) and \(x_1^+\) be the two vertices adjacent to \(x_1\) on the rim of the underlying wheel of \(G_1\). The edge cut \(C=\partial_G(V(G_1)\setminus\{x_1\})\) is nontrivial. Since \(G\) is a brick, \(C\) is not tight. Both shores of \(C\) have odd order, so there is a perfect matching \(M\) with \(|M\cap C|\geq 3\). Similar to the discussion in Case 2, \(c_1x_1^\varepsilon\) is a forcing edge of \(G\) and \(|\partial_G(x_1^\varepsilon)\cap C|=1\), where \(\varepsilon\in \{-,+\}\). Since \(C\) is covered by \(\{c_1,x_1^-,x_1^+\}\), there is a vertex \(z\in V(R_2)\) such that \(c_1z\in M\cap C\). Since \(M\cap C=\{c_1z,\partial_G(x_1^-)\cap C, \partial_G(x_1^+)\cap C\}\), see Figure 2 (c), \(z\) is adjacent to neither \(x_1^-\) nor \(x_1^+\), and thus \(\partial_G(z)\cap C=\{c_1z\}\). By Proposition 7 (i), \(c_1z\) is not a forcing edge of \(G\), and every rim edge incident with \(z\) in \(G_2\) is not forcing in \(G\). So \(z\) is incident with no forcing edge of \(G\), a contradiction.
In all the cases discussed above, we can always find a contradiction. Hence our assumption must be false, and \(G\) contains at least one vertex that is not incident with any forcing edge. ◻
3 Proof of Theorem 1↩︎
We will present a proof of Theorem 1 in this section. Firstly, we have the following Lemma.
Lemma 16. If \(G\) is a nonsolid brick with property \(\mathcal{P}\), then \(G\) is isomorphic to a splicing of \(W\) and \(G'\), where \(W\) is an odd wheel up to multiple edges, and \(G'\) is a brick with property \(\mathcal{P}\).
Proof. Applying Theorem 3, there exist two disjoint vertex subsets \(X'\) and \(X''\) of \(G\) such that \(G/\overline{X'}\) is a solid brick, \(G/\overline{X''}\) is a brick, and the graph \(H\) obtained from \(G\) by contracting \(X'\) and \(X''\) to single vertices \(x'\) and \(x''\), respectively, is bipartite and matching covered.
Let \(W=G/(\overline{X'}\rightarrow \overline{x'})\) and \(G'=G/(\overline{X''}\rightarrow \overline{x''})\). By Proposition 7, all vertices of \(W\), except possibly the contraction vertex \(\overline{x'}\), are incident with forcing edges. By Lemma 13, \(W\) is an odd wheel up to multiple edges. We claim that \(H\) has only the two contraction vertices \(x'\) and \(x''\). Otherwise Lemma 5 gives a vertex in \(H\) that is not incident with any forcing edge. Thus \(G\cong W(\overline{x'})\odot G'(\overline{x''})\). Let \(C\) be the splicing cut.
Since \(G\) has the property \(\mathcal{P}\), every vertex of \(G'\) except possibly \(\overline{x''}\) is incident with a forcing edge of \(G\), which is also a forcing edge of \(G'\) by Proposition 7. Since \(V(W)\setminus\{\overline{x'}\}\neq\emptyset\) and \(G\) has the property \(\mathcal{P}\) , \(V(W)\setminus\{\overline{x'}\}\) contains a vertex that is incident with a forcing edge of \(G\), say \(e\). Let \(M_e\) be the unique perfect matching of \(G\) containing \(e\). By Proposition 7, \(|M_e\cap C|=1\). Note that the unique edge in \(M_e\cap C\) corresponds to an edge \(e'\) of \(G'\). Once by Proposition 7, \(e'\) is a forcing edge of \(G'\). Since \(\overline{x''}\in V(e')\), \(\overline{x''}\) is incident with a forcing edge of \(G'\). From the above discussion, \(G'\) has the property \(\mathcal{P}\). ◻
Proof of Theorem 1. If \(G\) is an odd wheel, then every vertex is incident with a spoke, and every spoke is a forcing edge; hence \(G\) has the property \(\mathcal{P}\).
Conversely, suppose that the theorem is false, and choose a counterexample \(G\) with minimum number of robust cuts. Then \(G\) is a simple brick with the property \(\mathcal{P}\), but \(G\) is not an odd wheel. By Lemma 13, \(G\) is not solid. By Theorem 3, the number of robust cuts in \(G\) is at least one. By Lemma 16, \(G\) is isomorphic to a splicing of \(W\) and \(G'\), where \(W\) is an odd wheel up to multiple edges, and \(G'\) is a brick with the property \(\mathcal{P}\). Naturally, the underlying graph of \(G'\) satisfies the property \(\mathcal{P}\). By the minimality of \(G\), the brick \(G'\) is an odd wheel up to multiple edges. Thus \(G\) is a brick obtained by splicing two odd wheels up to multiple edges, contradicting Lemma 15. Therefore the theorem follows.