Bertrand Guenin

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.

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 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,

Given a pair of signed-graphs \((G_1,\Sigma_1)\), \((G_2,\Sigma_2)\) for which \(ecycle(G_1,\Sigma_1)\) \(=\) \(ecycle(G_2,\Sigma_2)\), what is the relationship between \((G_1,\Sigma_1)\) and \((G_2,\Sigma_2)\)?
Given a pair of grafts \((G_1,T_1)\), \((G_2,T_2)\) for which \(ecut(G_1,T_1)\) \(=\) \(ecut(G_2,T_2)\), what is the relationship between \((G_1,T_1)\) and \((G_2,T_2)\)?

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.

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,

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,

Theorem 2

Let \(G_1, G_2\) be inequivalent graphs (with the same edge label). Then the following are equivalent,

(a) There exists \(\Sigma_1,\Sigma_2\) such that \(ecycle(G_1,\Sigma_1)=ecycle(G_2,\Sigma_2)\),
(b) There exists \(T_1,T_2\) such that \(ecut(G_1,T_1)=ecut(G_2,T_2).\)

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.

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_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 (Ohio State Univ. 1982), Shih 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\).

2. Bridges in signed graphs

A path with at least one edge with ends having degree at least \(3\) and internal vertices having degree \(2\) is a segment. A graph \(S\) is a \(G\)-subdivision where \(G\) is a graph, if \(S\) is obtained by replacing each edge be a non-empty set of series edges. If \(S\) is a subgraph of \(H\) and \(S\) is a \(G\)-subdivision, then \(S\) is a \(G\)-subdivision in \(H\). Consider a subgraph \(S\) of a graph \(H\). An \(S\)-bridge in \(H\) is a subgraph \(B\) of \(H\) such that \(EB\cap ES=\emptyset\) and either \(EB\) consists of a single edge with both ends in \(VS\), or for some component \(C\) of \(H\setminus VS\), \(B\) is induced by the edges of \(H\) with at least one end in \(VC\). We say that \(VB\cap VS\) are the attachments of \(B\). An \(S\)-bridge \(B\) in \(H\) is stable if no segment of \(S\) includes all the attachments of \(B\).

Theorem 3

Let \(G,H\) be graphs where \(G\) has minimum degree \(3\) and where \(H\) is \(3\)-connected and simple. If there exists a \(G\)-subdivision in \(H\) then there exists a \(G\)-subdivision \(S\) in \(H\) where all \(S\)-bridges are stable.

Bridges have been studied extensively and play an important role in structural graph theory. The theory of bridges has been used to prove such well-known results as Kuratowski's Theorem and Tutte's famous result that every 4-connected graph with at least 4 vertices has a Hamiltonian cycle.

Preserving parity of cycles

Let \(G\) be a graph with minimum degree three and let \(S\) be a \(G\)-subdivision. For each \(e\in EG\) denote by \(Z_e\) the corresponding set of series edges in \(S\). Define \(\Phi: 2^{EG}\rightarrow 2^{ES}\) where \(\Phi(L):=\cup_{e\in L}EZ_e\). Observe that edges \(L\subseteq EG\) form a cycle of \(G\) if and only if edges \(\Phi(L)\subseteq ES\) form a cycle of \(S\). However, \(|L|\) and \(|\Phi(L)|\) may have different parities. We want to extend the theory of bridges to a framework where \(\Phi\) preserves parity of cycles.

A signed graph is a pair \((G, \Sigma)\) where \(G\) is a graph and \(\Sigma\subseteq EG\). The edges of \(G\) in \(\Sigma\) are odd and the other edges are even. The parity of a subgraph \(F\) of \(G\) is defined as the parity of \(|EF\cap \Sigma|\). A signed graph \((S,\Lambda)\) is a \((G,\Sigma)\)-subdivision if \(S\) is a \(G\)-subdivision and for every \(e\in EG\) we have \(e\in\Sigma\) if and only if the corresponding segment \(Z_e\) of \(S\) satisfies \(|EZ_e\cap\Lambda|\) odd. Then edges \(L\subseteq EG\) form a cycle of \(G\) if and only if \(\Phi(L)\) form the edges of a cycle of \(S\), moreover \(L\) is odd in \((G,\Sigma)\) if and only if \(\Phi(L)\) is odd in \((S,\Lambda)\). Hence, our definition of subdivision for signed graphs preserve parity of cycles. If \((S,\Lambda)\) is a subgraph of \((H,\Gamma)\) and \((S,\Lambda)\) is a \((G,\Sigma)\)-subdivision, then \((S,\Lambda)\) is a \((G,\Sigma)\)-subdivision in \((H,\Gamma)\).

A natural question is whether Theorem 3 extends to the context of signed graphs. Namely,

Question:

Consider signed graphs \((G,\Sigma)\) and \((H,\Gamma)\) where \(G\) has minimum degree \(3\) and \(H\) is \(3\)-connected and simple. Assuming that there exists a \((G,\Sigma)\)-subdivision in \((H,\Gamma)\), does there exists an \((G,\Sigma)\)-subdivision \((S,\Lambda)\) in \((H,\Gamma)\) where all \(S\)-bridges are stable?

Alas this is not the case. The next figure shows a configuration of unstable bridges with all attachments in segment \(Z\) that cannot be eliminated by choosing a different subdivision. Dashed lines correspond to odd edges and solid lines correspond to even edges (in particular, all edges of \(Z\) are even). The shaded vertex \(x\) is the only attachments of a stable bridges on \(Z\).

Assuming \(3\)-connectivity we show we can find a \((G,\Sigma)\)-subdivision \((S,\Lambda)\) in \((H,\Gamma)\) where all unstable \(S\)-bridges fall into one of three classes, illustrated by \(B_1,B_2,B_3\) in the previous figure. If we assume \(4\)-connectivity then, we can find a subdivision where all unstable bridges are of the same type.

Theorem 4

Consider signed graphs \((H,\Gamma)\) and \((G,\Sigma)\) where \(G\) has minimum degree \(3\) and where \(H\) is \(4\)-connected and simple. Suppose that there exists a \((G,\Sigma)\)-subdivision in \((H,\Gamma)\). Then there exists a \((G,\Sigma)\)-subdivision \((S,\Lambda)\) in \((H,\Gamma)\) such that for every bridge \(B\) that has all attachments in a segment \(Z\), \(B\) has distinct attachments \(s_1,\ldots,s_p, t_1,\ldots,t_q\) where \(p,q\geq 1\), and the vertices \(s_1,\ldots,s_p,t_1,\ldots,t_q\) appear on \(Z\) in the order stated. If \(w\in V(s_1Zt_q)\setminus\{s_1,t_q\}\) is an attachment of a stable \(S\)-bridge, then \(w\in V(s_pZt_1)\). Moreover, \(\cup_{i=1}^p \delta_B(s_i)\) is a signature of \((H,\Gamma)| EB\cup EZ\).

Here given a path \(Z\) and vertices \(x,y\) of \(Z\), \(xZy\) denotes the subpath of \(Z\) with ends \(x,y\).