Let $G$ be an undirected connected graph. $\forall v∈V(G)$, $G-v$ (remove the node and all of its relevant edges from the graph) is still a connected graph. Besides, the fundamental cut-set matrix $S$ of $G$ has an even number of ones in each of its rows. Prove that there is an Eulerian circuit in graph $G$.
I have come across the problem and thought about it for quite a long time, but the progress I have yet made is still very little. Here is what I have tried:
First, from the first condition given, I find that every node in the graph should have a degree $d\ge2$, for otherwise by deleting the only node it connects one can split the graph into two separate parts. Also, it tells me that each node is on a circuit. However, I have no idea how to make further use of it.
Then, I tried to analyze the answer to see if the proposition can be reduced to a simpler one. Let the adjacent matrix be $B$, the fundamental loop matrix be $$C=\begin{pmatrix}I & C_f\end{pmatrix}, $$ and the fundamental cut-set matrix be $$S=\begin{pmatrix}S_f & I\end{pmatrix}. $$ Denote the vectors with all one's be $\vec{1}$ (for convenience, I omit the dimension), and assign directions for the edges (it suffices to prove that a certain distribution of directions leads to an Eulerian circuit). Eulerian circuit exists if and only if each node has the same amount of in-degree and out-degree, i.e., $$B\cdot\vec{1}=\vec{0}. $$ Given that $BC^T=0$, I thought it might suffice to prove that $\vec{1}\in \mathcal{R}(C^T)$, i.e., $$\vec{1}= C_f^T\cdot\vec{1}=-S_f\cdot\vec{1}$$ since the left part $I$ of $C$ ensures that we have to take the summation of the rows to create a $\vec{1}$. This is equal to $$S\cdot\vec{1}=\begin{pmatrix}S_f & I\end{pmatrix}\cdot\vec{1}=S_f\cdot\vec{1}+\vec{1}=\vec{0}. $$ Therefore, all I need to do is to show each row of $S$ sum up to 1, which means that every cut-set of $G$ has the same amount of edges with the same direction with the cut-set and with the opposite, i.e., "there is an equal number of edges pointing toward different directions in arbitrary cut-set".
That's all my progress now. I have no idea what I can derive from the condition "the fundamental cut-set matrix $S$ of $G$ has an even number of ones in each of its rows." I even don't know whether I am on the right track. Is there anyone who can help me out?
The question is from a book (戴一奇. (1995). 图论与代数结构) about Graph Theory and Algebraic Structure (used as the textbook in our Discrete Math course). It is Problem 13 on Exercise 3.
Note. There is a similar question posted a while before by another (Prove that there is an Euler circuit in graph G), but the question seems to have not very much detailed explanation and still no answers yet. So I decided to rephrase it and post it again.
The definitions are new to me, so let me repeat them to see if they are correct.
We have an undirected connected graph $G$ and we've chosen a particular spanning tree $T$ of $G$. For every edge $e \in E(T)$, there is a corresponding fundamental cut-set: the set of all edges of $G$ between the two components of $T-e$.
Assuming the rows of the fundamental cut-set matrix give the fundamental cut-sets, the condition we are given is that every fundamental cut-set has an even number of edges.
In a graph with an Eulerian circuit, all cut-sets have an even number of edges: if the Eulerian circuit starts on one side of the cut-set, it must cross an even number of times to return where it started, and these crossings use every edge of the cut-set once. Conversely, if all cut-sets in a graph have an even number of edges, then in particular, all vertex degrees are even: the set of edges out of a vertex is a cut-set! So a connected graph is Eulerian if and only if all cut-sets have an even number of edges.
So it makes sense to try to prove this statement from the weaker statement that all fundamental cut-sets have an even number of edges.
Theorem. Every cut-set is a symmetric difference of fundamental cut-sets.
Proof. Take an arbitrary cut-set $E(X,Y)$ where $X$ and $Y$ partition $V(G)$. We'll show that $E(X,Y)$ is the symmetric difference of all the fundamental cut-sets given by edges in $E(T) \cap E(X,Y)$.
To see this, let $vw$ be any edge of $G$. The fundamental cut-sets containing $vw$ are exactly the ones given by edges on the unique $v-w$ path in $T$. Therefore the symmetric difference we're taking contains $vw$ iff an odd number of edges on this path cross between $X$ and $Y$. This happens iff $v$ and $w$ are on different sides of the cut, which happens iff $vw \in E(X,Y)$. $\qquad\square$
If two sets $A,B$ both have an even number of elements, then their symmetric difference $(A\cup B) - (A \cap B)$ also has an even number of elements, because $$|A \cup B| - |A \cap B| = (|A| + |B| - |A \cap B|) - |A \cap B| = |A|+|B|-2|A\cap B|$$ and all three terms of the final expression are even. By induction, the symmetric difference of any number of even sets is even. So if all fundamental cut-sets are even, then by the argument above, all cut-sets are even, and we are done.