On the basis of the direct product of paths and wheels (Q1912343)

For (finite, undirecte, simple) graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), the direct product \(G_1 \wedge G_2\) is defined to be the graph \(G = (V,E)\) with vertex set \(V = V_1 \times V_2\) and edge set \[ E = \{uv \mid u = (u_1, u_2) \in V,\;v = (v_1, v_2) \in V,\;u_1v_1 \in E_1, \quad u_2 v_2 \in E_2\}. \] The cycle space \(C(G)\) of a graph \(G = (V,E)\) with \(p\) vertices, \(q\) edges, and \(\omega\) (connected) components consists of all subsets of \(E\) each of which corresponds to a (possibly empty) subgraph of \(G\) whose components are Eulerian graphs. It is known that \(C(G)\) is a subspace of the \(q\)-dimensional vector space over the Galois field \(GF(2) = \{0,1\}\) formed (in the usual way) by the subsets of \(E\), that \(C(G)\) is generated ``by the cycles of \(G\)'' (i.e. by all subsets of \(E\) corresponding to (elementary) cycles of \(G)\), and that its dimension is the cyclomatic number \(\gamma (G) = q - p + \omega\). A cycle basis of \(G\) is a basis of the space \(C (G)\) consisting of cycles of \(G\). For a cycle basis \(B\) of \(G\) and an edge \(e \in E\), the number of cycles in \(B\) containing \(e\) is denoted by \(f_B(e)\), and \(B\) is said to be \(k\)-fold if \(f_B (e) \leq k\) for every \(e \in E\). The basis number \(b(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has a \(k\)-fold cycle basis. Let \(P_m\) denote a path with \(m\) vertices, and \(W_n\) a wheel with \(n\) vertices. Now, the following statements are proved: (1) \(b(P_2 \wedge W_n) \leq 2\) and therefore, according to a result of \textit{S. MacLane} [Fundam. Math. 28, 22-32 (1937; Zbl 0015.37501)], \(P_2 \wedge W_n\) is planar for \(n \geq 4\); and (2) \(b(P_m \wedge W_n) = 3\) (and therefore, \(P_m \wedge W_n\) is nonplanar) for all \(m \geq 3\) and \(n \geq 4\).