Bertrand Guenin - Whitney

Whitney'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 2-flip of \(G.\) We call a 1-flip 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,

Generalizing the problem.

A signed-graph 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 signed-graphs 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 even-cuts. 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 non-trivial.

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 signed-graphs with same even-cycles and a pair of grafts with the same even cuts. This is part of a general phenomena,

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,

• [1] B. Guenin, I. Pivotto, P. Wollan, Relationships between Pairs of Representations of Signed Binary Matroids, February 2013, SIAM Journal on Discrete Mathematics 27(1). https://doi.org/10.1137/100798442

Shih's theorem.

In his PhD thesis Shih investigated the following problem,

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_1|-|VG_1|+1\) and \(\dim(cycle(G_2))\) \(=\) \(|EG_2|-|VG_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\)).

• [2] Shih C. H., On graphic subspaces of graphic spaces, Phd. dissertation, Ohio State Univ. (1982)

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,

• [3] Z. Ferchiou, B. Guenin, A Short Proof of Shih’s Isomorphism Theorem on Graphic Subspaces. Combinatorica (2020). https://doi.org/10.1007/s00493-020-3972-9

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,

• [4] B. Guenin, C. Heo, I. Pivotto, Graphs with the same even-cycles, manuscript.