# Graph Theory+ Number Theory.

Problem: Let $G$ be a connected graph. Let $T$ be a spanning tree of $G.$ Prove that $T$ contains a spanning subgraph $T'$ such that, for each vertex $v$, the degree of $v$ in $G$ and the degree of $v$ in $T'$ are equal modulo $2.$

I tried a couple of examples but was unable to get some intuition for this problem, any hints/suggestions will be much appreciated.

Here is an algebraic proof.Have you ever learned Data Structure(I major in computer science...)?A kind of matrix named incidence matrix is defined as below:It is a $|V|*|E|$ matrix on $GF(2)$.If edge $e_i=(v_i,v_j)$ then $(v_i,e_i)=1 , (v_i,e_j)=1$,else $(v,e)=0$.

It is deep night in China and I'm really sleepy,but I really want to offer help.so I draw a picture for you without using Latex to illustrate the matrix and the graph,easy to see,they are corresponding with each other.

$\textbf{Lemma 1}$：The columns of matrix of spanning tree $T$(which is surrounded by the dotted line) is the maximal linear independent set of column space of incidence matrix of G(denoted by $M$).

$\textbf{Proof}$.They are linear independent because there are no circles in a tree(If columns are linear dependent,those edges will form a circle).And it's maximal because add an edge to the spanning tree will add a circle.

$\textbf{Lemma2}$ There are $|V|-1$ columns in spanning tree matrix.

$\textbf{Proof}$ It's easy.For a tree,$|E|=|V|-1$.

$\textbf{Lemma3}$ If $M$ is a (incidence) matrix of a spanning tree,then it does not contain a zero row.

Why?Because in a spanning tree,every vertex is connected to at least one edge,and only one.

$M$ is denoted as the incidence matrix of $G$. Then our aim is to:$\textbf{Select columns from spanning tree matrix and form them into a new matrix N,such that}$ $\textbf{for every row of$M,N$,the sum of elements of$M$equals the sum of elements of$N$.}$The sum here means exclusive or $\oplus$.Because the sum of rows indicate the degree of vertexs. For example,In the picture provided,$deg(v_1)=3$,and the sum of first row is $3$.If in $GF(2)$,$3$ mod $2$ = $1$,and $1 \oplus 1 \oplus 1 = 1$.

Then how to do?If the first row does not satisfy our aim,choose a column $j$ that $M_{1,j}$=1(As was proved in Lemma 3,no zero row!) and delete that column(So first row must satisfy).And do the same again on the second row...

Sometimes $T^{'}$ has to be an empty graph,for example,$G$ is a triangle.Three vertexs,three edges.

• Hi, I am not able to follow your argument, towards the end (after the bold part). Could you please elaborate? Commented Apr 27, 2017 at 6:59
• Indeed,only Lemma3 is necessary.The degree of a vertex is the sum of matrix elements related to that vertex.So the parity is the exclusive or of matrix elements related to that vertex.So we only need to delete or choose several columns of the spanning tree matrix(surrounded by dots),such that for every row,the exclusive or of spanning tree matrix equals the exclusive or of graph matrix $M$.If first row does not satisfies Commented Apr 27, 2017 at 10:36
• our need,then we delete a column j,which $M_{1,j}=1$.(Delete the column,whose first row is 1).That's well defined,since as proved in Lemma3,no zero row is found in the spanning tree matrix,so we always can choose a column whose first row equals 1.Do this for $|E|_{SpanningTree}$ vertexs in the spanning tree because we can at most delete $|E|_{SpanningTree}$ edges.After that,at most one vertex does not satisfy the condition.But since the sum of degrees of matrix is even,if $|V|_{SpanningTrees}-1$ vertexs satisfy the condition(bold part),that the last matrix always satisfy it. Commented Apr 27, 2017 at 10:43