# How to prove all connected graphs with even number of edges and without loop and multiple edges can be divided into pairs of adjacent edges?

First I try to use induction.

Way1 :
I think this it like repeat deleting two adjancent edges in graph.
the two delete edge contain three point,supposed they are a,b,c,there are three cases:

1. If (a,b) (a,c) exist but (b,c) not exist.If delete (a,b)(a,c),the remained graph is still a graph with even edges
2. If (a,b) (b,c) exist but (a,c) not exist. If delete (a,b)(b,c),remained a graph withm even edges
3. If there is a cycle , such as (a,b)(b,c)(a,c). this has two cases

case 2.1 after deleting, G is still connected , this is ok
case 2.2 after deleting, G become two conponent G1 and G2,for example,if delete (a,c) and (b,c) ,and c has no another edge to the conponent which contains vertice a and vertice b. this again be two case.

 case 2.2.1 Both G1 and G2 has even edges, this is ok
case 2.2.2 Both G1 and G2 has odd edges, this is bad!!!!


I don't know how to prove in case 2.2 so I come to another way.

Way2 :
First find a edge e1 and then we should find another e2 to match it.After deleting e1 e2 ,there are two case

case 1 G is connected, ok
case 2 w(G)=2, suppose G-e1 = G1 + e2 + G2 , then in G1 must has even edges and G2 has odd edges. the most important one is to find a e2 in G2 .

I don't know how to do when G2-e2 become two unconnect odd conponent!!

can anyone help me ? Thanks~

• Prove that there is always at least one pair of adjacent edges that can be deleted without disconnecting the graph. – Paul Sinclair Sep 9 '15 at 2:24
• @PaulSinclair: That statement isn't true, though. Consider a tree with an even number of edges, then any edge deletion disconnects the graph. (Some of the resulting connected components might consist of single vertices, but they still exist.) – Mark Dickinson Sep 9 '15 at 12:51
• @MarkDickinson - in this problem only the edges matter. It should be understood that removing edges includes moving any isolated vertices created. – Paul Sinclair Sep 9 '15 at 22:57

I got an idea ! use strong induction . suppose for all G with 2n vertice satisfied the statement. Then we shuld proof it is true when |V|=2(n+1)
when |G| = (2n+1) , just like add two edge e1 , e2 and we delete e1 and e2 ,either one pair or two pair of edges,then we get G', there are three cases in G':

1. w(G') = 1 : G' is connected ,then we G' with 2n or 2(n-1) vertice satisfied condition
2. w(G') = 2 : If both two conponent of G' are odd edges ,we can let e1 and its adjacent edge choose one edge in their adjacet component ,and both conponent will conotain even edges ; if both conponent contains even edge,it satisfy;
3. w(G') = 3 : G' = G'' + (e1,ei) + (e2,ej) , G'' contains be even edges

to conclude G with 2(n+1) satisfies the condition.

In any tree with more than $2$ vertices one of the following must happen:

• A leaf is connected to a vertex of degree $2$
• two leaves are adjacent to the same vertex.

Proof: Suppose neither of these things happen. mark every leaf of the tree and then remove all of them, we obtain a graph in which every vertex has degree at least $2$. (notice that if there are more than two vertices then not every vertex is a leaf).

Suppose that there is a counterexample to the theorem we desire to prove. Let $G$ be a counterexample with the least possible number of vertices, and among the counterexamples with the least possible number of vertices pick a counterexample with the least possible number of edges.

Pick a spanning subgraph $T$ of $G$.

Suppose that a leaf $l$ is connected to a vertex $v$ of degree $2$ (suppose $w$ is the other neighbout of $v$). Notice that after removing vertices $(l,v)$ and $(v,w)$ we get a graph in which only vertices $l$ and $v$ might be separated from the rest (but even then there is no edge between them). So we obtain a graph in which every component has an even number of edges, a contradiction.

Suppose that two leaves $l$ and $m$ contain a common neighbour $v$. If the edge $(l,m)$ exists in $G$, then after removing edges $(l,m)$ and $(l,v)$ we obtain a graph in which the only possible separated vertex is $l$, this would be a contradiction because every connected component of the resulting graph would have an even number of edges. On the other hand, if $(l,m)$ does not exist in $G$, after removing edges $(l,v)$ and $(m,v)$ we obtain a graph in which the only possible separated edges are $l$ and $m$, but there is no edge between them. So we obtain a graph in which every component has an even number of edges, a contradiction.

If suffices to prove that in every connected graph $G(V,E)$ with $|E|\overset{2}{\equiv} 0$, one can set directions for every edge $e$ in $G$ which for evey vertex $v$, $d^{+}(v)$ is an even number. Then we would take pairs of exiting edges from every vertex, as a path with length of $2$. Here is an example: First, set an arbitrary direction for every edge in $G$. If there is no vertex $v$ such that $d^{+}(v) \overset{2}{\equiv} 1$ , we are done. so suppose that there exists a vertex $v$ with $d^{+}(v)$ being odd. from a well-known lemma, we know that $\sum_{v \in V} d^{+}(v) = |E| \overset{2}{\equiv} 0$. Hence $\exists \, u\in V, u \neq v: d^{+}(u) \overset{2}{\equiv} 1$. Since $G$ is connected, there is an [undirected] path from $v$ to $u$. We invert the direction of every edge in this path. It is easy to see that the parity of exiting degree of vertices in this path, despite $u$ and $v$, remain unchanged; and now $d^{+}(u)\overset{2}{\equiv}d^{+}(v)\overset{2}{\equiv}0$. As $V$ is finite, this operation must end. Thus every vertex in $G$ has an even number of exiting edges, done.

I come up with an idea : if I reconstruct a new graph like this:
take all edges in G as vertice in G' , if e1 and e2 have common vertice, then in G' , v1 and v2 have a edge.
then our question become : matching a connected graph G' with even vertice. This is easy, a connected tree has a subtree , then we delete vertice from all its leaves . QED!!

• yearh , this is not true, in such a tree a->b->c and b->d – tinyork Sep 9 '15 at 22:35