When can an edge subset of a graph be extended to become an element of its cycle space?

Question

Let $F$ be a set of edges in a graph $G$. Show that $F$ extends to an element of the cycle space of $G$ iff $F$ contains no odd cut.

The context for this exercise is the following: Let $G = (V,E)$ be a simple graph (i.e., a graph without parallel edges or loops). We can understand the power set $2^E$ (with the symmetric difference $\dotplus$ as addition) as vector space $\mathcal E(G)$ over $\mathbb F_2$. Many authors write also $GF(2)$ for $\mathbb F_2$. If $C$ is a cycle subgraph of $G$, then the edge set of $C$ is called a circuit. The vector subspace of $2^E$ generated by all circuits is called the cycle space $\mathcal C(G)$ of $G$. The above exercise asks when an arbitrary set of edges $F$ of $G$ can be extended to an element of $\mathcal C(G)$.

We can understand an element $W \in \mathcal E(G)$ as indicator map $W: E \to \mathbb F_2$ and define a bilinearform $\left\langle F, F'\right\rangle := \sum_{e \in E} F(e) \cdot F'(e) \in \mathbb F_2$ for $F, F' \in \mathcal E(G)$. So $\left\langle F, F'\right\rangle = 0$ iff $F$ and $F'$ have an even number of edges of $G$ in common. In general we have $\left\langle F, F'\right\rangle = 0$ if $F$ is any circuit and $F'$ is any cut of $G$.

I have the following suggestion for one of the two implications of the exercise (but I have no idea for the other implication).

Let $\emptyset\not= F \subseteq E(G)$ be a set of edges that extends to an element $C\in\mathcal C(G)$, i.e., $F \subseteq C$. Suppose $F$ contains an odd cut $D$, i.e., $D \subseteq F \subseteq C$.

Consider the following facts: $D \cap (C\setminus F) = \emptyset$ and $C\setminus F = C \dotplus F$ and $C = F \cup (C\setminus F) = F \dotplus (C\setminus F) = F \dotplus (C \dotplus F)$.

Since $C$ is a circuit and $D$ is a cut, it follows $0 = \left\langle C,D\right\rangle = \left\langle F \dotplus (C\setminus F),D\right\rangle = \left\langle F,D\right\rangle + \left\langle C\setminus F,D\right\rangle = 1 + 0 = 1$ which is a contradiction.

There is also a dual version of the exercise above (which could be of use): Let $F$ be a set of edges in a simple graph $G$. Show that $F$ extends to an element of the cut space $\mathcal C^*(G)$ of $G$ iff $F$ contains no odd circuit. For this equivalence I have a complete solution, but not for the original one.

Answer 1

I will use that characterization that a set of edges $E'$ is in the cycle space iff every vertex has even degree in the spanning subgraph with edge set $E'.$

As a lemma, note that for any graph $(V,E)$ and any subset $U$ of its vertices such that $|U\cap C|$ is even for each connected component $C$ of $(V,E),$ we can find a set of edges $E'$ such that in $(V,E'),$ each vertex in $U$ has odd degree and each vertex in $V\setminus U$ has even degree. This is because we can pair up the elements of $U$ arbitrarily within each connected component, pick any path joining each pair, and take the symmetric difference (exclusive-or) of the edges in these paths.

Now, given an arbitrary graph $(V,E)$ and a set of edges $F$ not containing any odd cut, define $U$ to be the set of vertices of odd degree in $(V,F).$ Within each connected component $C$ in $(V,E\setminus F),$ there are an even number of vertices in the set $C\cap U$ - otherwise the set of edges between $C$ and $V\setminus C$ is an odd cut. So we can use the previous lemma to get a set of edges $F'\subseteq E\setminus F$ such that each vertex has even degree in $E\setminus (F\cup F').$ This means $F\cup F'$ is an extension of $F$ to an element of the cycle space.