Bertrand Guenin  WhitneyWhitney's theorem.By a cycle in a graph we mean a subset of the edges with the property that every vertex of the subgraph induced by these edges has even degree. We write \(cycle(G)\) for the set of all cycles of \(G\) and write \(cut(G)\) for the set of all cuts (also viewed as sets of edges) of \(G.\) We can view \(cycle(G)\) and \(cut(G)\) as orthogonal binary vector spaces. Consider a graph \(G\) with a two vertex cutset. If \(G'\) is obtained from \(G\) by flipping the subgraph on one side of the \(2\)separation as indicated in the following figure then \(G'\) is a 2flip of \(G.\) We call a 1flip the identification of two vertices in distinct components or splitting two blocks into different components. Two graphs are equivalent if they are related by a sequence of \(1\)flips and \(2\)flips. In 1933 Whitney proved that, Theorem 1
If \(cycle(G)=cycle(G’)\) or equivalently \(cut(G)=cut(G’)\) then \(G\) and \(G'\) are equivalent. In particular, if \(G\) or \(G'\) is \(3\)connected then \(G=G’.\) Generalizing the problem.A signedgraph is a pair \((G,\Sigma)\) where \(G\) is a graph and \(\Sigma\subseteq EG.\) A cycle \(C\) is even (resp. odd) if \(C\cap\Sigma\) is even (resp. odd). We write \(ecycle(G,\Sigma)\) for the set of all even cycles of \((G,\Sigma).\) A graft is a pair \((G,T)\) where \(G\) is a graph and \(T\subseteq VG\) where \(T\) is even. If there exists a component of \(G\) with an odd number of vertices in \(T\) then every cut of \((G,T)\) is defined to be even. Otherwise, a cut \(\delta(U)\) is even (resp. odd) if \(T\cap U\) is even (resp. odd). We write \(ecut(G,T)\) for the set of all even cuts of \((G,T).\) We are interested in generalizing Theorem 1 to signedgraphs and grafts. More precisely, we are interested in the following two problems,
Observe that \(ecycle(G_i,\Sigma_i)\) \(=\) \(cycle(G_i)\) when \(\Sigma_i=\emptyset.\) Hence, Problem 1 generalizes the problem of characterizing when two graphs have the same cycles. Similarly, \(ecut(G_i,T_i)\) \(=\) \(cut(G_i)\) when \(T_i=\emptyset.\) Hence, Problem 2 generalizes the problem of characterizing when two graphs have the same cuts. Suppose \(G_1\) and \(G_2\) are equivalent. Then \(ecycle(G_1,\Sigma_1)\) \(=\) \(cycle(G_2,\Sigma_2)\) exactly when \(\Sigma_1\) and \(\Sigma_2\) are related by resigning, and \(ecut(G_1,T_1)\) \(=\) \(ecut(G_2,T_2)\) exactly when a \(T_1\)join of \(G_1\) is a \(T_2\)join of \(G_2\). Hence, for equivalent graphs \(G_1\) and \(G_2\) problems 1 and 2 are solved and it suffices to restrict our attention to the case where \(G_1,G_2\) are not equivalent. Consider the following example. Denote by \(G_1\) the (edge labeled) graph on the left and by \(G_2\) the (edge labeled graph) on the right. Note that \(G_1\) and \(G_2\) are not equivalent. Define, \[ \Sigma_1=\{1,3,6,7,12\}\quad\mbox{and}\quad\Sigma_2=\{1,2,3,4,5\}. \] Then observe that \((G_1,\Sigma_1)\) and \((G_2,\Sigma_2)\) have the same set of even cycles. Hence, an answer to Problem 1, will involve the aforementioned construction. Suppose we now define \(T_1\) and \(T_2\) to denote the set of all vertices in \(G_1\) and \(G_2\) respectively. Then observe that \((G_1,T_1)\) and \((G_2,T_2)\) have the same evencuts. Hence, an answer to Problem 2, will involve the aforementioned construction as well. The previous examples show in particular that even assuming high connectivity for \(G_1\) and \(G_2\) the answer to problems 1 and 2 is nontrivial. Problem 1 and Problem 2 are equivalent.We have now seen a pair of inequivalent graphs for which we were able to construct both a pair of signedgraphs with same evencycles and a pair of grafts with the same even cuts. This is part of a general phenomena, Theorem 2
Let \(G_1, G_2\) be inequivalent graphs (with the same edge label). Then the following are equivalent,
In addition if (a) respectively (b) hold then \(\Sigma_1,\Sigma_2\) are unique (up to resigning) and \(T_1,T_2\) are unique. We say that a pair of inequivalent graphs for which (a), (b) hold in the previous Theorem, are siblings. Thus Problem 1 and Problem 2 are equivalent to the problem of characterizing siblings. Theorem 2 can be found in the following paper,
Shih's theorem.In his PhD thesis Shih investigated the following problem, Given a pair of graphs \(G_1,G_2\) where \[ (\star)\quad\quad cycle(G_1)\subseteq cycle(G_2)\quad\&\quad\dim(cycle(G_1))=\dim(cycle(G_2))1, \] what is the relationship between \(G_1\) and \(G_2\)? Condition (\(\star\)) holds, if and only if for some \(\Sigma_2\) we have \(cycle(G_1)=ecycle(G_2,\Sigma_2)\) where \((G_2,\Sigma_2)\) has a least one odd cycle. Hence, the problem that Shih investigated is a special case of Problem 1. So what are pairs of graphs that satisfy (\(\star\))? As an example consider a connected graph \(G_1\) with distinct vertices \(a\) and \(b\) and let \(G_2\) be obtained from \(G_1\) by identifying vertices \(a\) and \(b\). Then clearly, every cycle of \(G_1\) is a cycle of \(G_2\). Moreover, as \(\dim(cycle(G_1))\) \(=\) \(EG_1VG_1+1\) and \(\dim(cycle(G_2))\) \(=\) \(EG_2VG_2+1\), we have \(\dim[cycle(G_1)]=\dim[cycle(G_2)]1\). This is not the only construction. Consider the following pair of graphs where \(G_1\) is the graph on the left and \(G_2\) the graph on the right. Then the pair \(G_1, G_2\) also satisfies (\(\star\)). In his PhD thesis, characterizes the exact relation between pairs of graphs satisfying (\(\star\)).
Unfortunately, this result was never published and has been largely forgotten. It is important, however, and has found applications in the theory of graphic frame matroids for instance. We give a more accessible proof of his result in the following paper,
The general problem.Consider the general problem again, namely what is the relationship between a pair of siblings \(G_1\) and \(G_2\)? Recall that \(G_1,G_2\) are siblings if they are not equivalent and for some \(\Sigma_1,\Sigma_2\), \(ecycle(G_1,\Sigma_1)\) \(=\) \(ecycle(G_2,\Sigma_2)\) or equivalently for some \(T_1,T_2\), \(ecut(G_1,T_1)\) \(=\) \(ecut(G_2,T_2)\) for some \(T_1,T_2\). We give a complete answer for the case where both \(G_1\) and \(G_2\) are \(4\)connected. Informally speaking the result says that either we can explain the relationship between \(G_1\) and \(G_2\) using Shih's theorem, or \(G_1\) and \(G_2\) are as in the previous example where \(G_1\) and \(G_2\) are both isomorphic to \(K_6\). The following will be ready soon,
