3
$\begingroup$

Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd number of these edges.

First observation is that once you have selected a set $E$, the unselected edges don't really matter much. They only matter because we need the graph to be connected. So, we can remove a number of edges of this graph until we get a tree. If we can create a set $E$ using the edges of this tree satisfying the required conditions, then this $E$ will also satisfy the conditions for the original graph.

So, to simplify things, assume we have a tree with an even number of vertices. This tree must have leaves. It is necessary that $E$ must contain the edges incident with these leaves.

Now I am stuck. Ideas that I've had include strong induction, colouring etc..

How do I proceed?

Thanks

$\endgroup$
3
$\begingroup$

You would like to prove a connected graph with an even number of vertices has a subgraph in which every vertex has odd order. In fact much more is true.

We call a parity designation $\sigma$ of $G$ a function that assigns to each vertex $v$ of $G$ a desired parity for its degree(odd or even), with the only restriction that there is an even number of vertices with odd desired parity.

We prove that given a parity designation $\sigma$ of $G$ there is a spanning subgraph of $G$ that satisfies that parity designation. We prove it by induction and via the use of spanning substrees.

Base case: If $G$ has $2$ vertices and connected then $G$ is $K_2$ and there are only two possible parity designations (even, even and odd,odd). It is easy to see they are satisfied by the subgraph with no edges and by $K_2$ itself.

Inductive step. $G$ has $n+1$ vertices . Since $G$ is connected it has a spanning subtree $T$. This tree has a leaf $v$. Notice that when we romve $v$ from $T$ the remaining graph is still connected, therefore when we remove $v$ from $G$ we obtain a connected graph $G'$ with $n$ vertices.

Case $1$: The parity designation $\varphi$ requires that $v$ is an even vertex. This is the "easy" case. Consider $\varphi$ restricted to $G'$. This is a parity designation (because $v$ is supposed to be even, so there is still an even number of vertices in $G'$ that should be odd). By induction there is a spanning subgraph $H'$ of $G'$ that satisfied $\varphi$ in $G'$. Notice the edge of $H'$ also satisfy $\varphi$ in $G'$ since they leave $v$ with degree $0$ which is even as desired.

Case $2$: The parity designation $\varphi$ requires that $v$ is an odd vertex. In this case let $w$ be the only neigbour of $v$ in the spanning subtree $T$. We define $\varphi'$, which is going to be a parity designation for $G'=G-v$. We let $\varphi'$ be equal to $\varphi$ for every value except $w$. In $w$ $\varphi'$ is going to be the opposite of $\varphi$ so if it was odd we cahnge it to even and if it was even we change it to odd. By induction there is a subgraph $H'$ of $G'$ that satisifies $\varphi'$. If we take the edges of $H'$ together with $wv$ we obtain a spanning subgraph of $G$ that satisfies $\varphi$. It is clear that it satisfies $\varphi$ for all values other than $u$ and $v$ since $\varphi'=\varphi$ in these values. In $u$ it also holds because without edge $uv$ the degree was the opposite of what $\varphi$ indicated, however after adding edge $uv$ it is the same as $\varphi$. $w$ also has the desired parity since the order of $w$ is $1$,which is odd.


What we have just proven implies what you want, just let $\varphi$ be the parity designation that asks for every vertex to be odd.(Notice this is a parity designation since the order of $G$ is even).


Second solution:

$G$ has an even number of vertices of odd order and hence $G$ has an even number of vertices of even order (Since there is an even number of vertices).We shall remove some of the edges of $G$ until every vertex has odd order. The strategy wel will use is the following: Split the vertices of even order into pairs. Let the pairs be $a1,b1$ and $a_2,b_2\dots a_k,b_k$ we will start adding and removing vertices until every vertex is odd. We start by making $a_1$ and $b_1$ odd (without changing the others). Because $G$ is connected we can find a path between $a_1$ and $b_1$.

Remove all of those edges, doing this makes $a_1$ and $b_1$ have odd degree (since their degree is reduced by $1$) and leaves evry other edge with the same parity(since the other affected vertices have their degree reduced by exactly $2$). The next thing we do is make $a_2$ and $b_2$ odd (without changing the others). Take the path between $a_2$ and $b_2$ and now what we do is slightly different, for each edge in the path there are two options, if the edge was removed previously, put it back in, if it was not removed then remove it). This process makes $a_2$ and $b_2$ odd since the degree of each vertex either increased by $1$ or decreased by $1$. On the other hand all other vertices stay with the same parity.

That is beacuse it can increase by $2$ (If the edges on both sides of the vertex were added back in) It can stay the same (if one edge was removed and the other was added back in) or it can decrease by two (if both edges where removed). We then proceed to making $a_3$ and $b_3$ both odd by using the same approach as for $a_2$ and $b_2$. We then make $a_4$ and $b_4$ odd and so on until we make $a_k$ and $b_k$ both odd. When we do this we will be finished.

$\endgroup$
11
  • $\begingroup$ Nice argument,+1. However, suppose I am given this question in a contest. My first approach wouldn't be to create a generalization and then try to prove it. It appears to me that the specific case in my question is harder to prove than the more general version, as there seems to be a problem when going from the inductive hypothesis to the inductive step. Can you suggest a way to solve only my problem? Thanks for the great answer. $\endgroup$
    – rah4927
    Jun 28 '15 at 17:29
  • $\begingroup$ $G$ has an even number of vertices of odd order and hence $G$ has an even number of vertices of even order (Since there is an even number of vertices).We shall remove some of the edges of $G$ until every vertex has odd order. The strategy wel will use is the following: Split the vertices of even order into pairs. Let the pairs be $a_1,b_1$ and $a_2,b_2$\dots $a_k,b_k$ we will start adding and removing vertices until every vertex is odd. We start by making $a_1$ and $b_1$ odd (without changing the others). Because $G$ is connected we can find a path between $a_1$ and $b_1$. $\endgroup$
    – Asinomas
    Jun 28 '15 at 17:35
  • $\begingroup$ Remove all of those edge, doing this makes $a_1$ and $b_1$ have odd degree (since their degree is reduced by $1$). The next thing we do is make $a_2$ and $b_2$ odd (without chainging the others). Take the path between $a_2$ and $b_2$ and now what we do is slightly different, for each edge in the path there are two options, if the edge was removed previously, put it back in, if it was not removed then remove it). This process makes $a_2$ and $b_2$ odd since the degree of each vertex either increased by $1$ or decreased by $1$. On the other hand all other vertices stay with the same parity. $\endgroup$
    – Asinomas
    Jun 28 '15 at 17:38
  • $\begingroup$ That is beacuse it can increase by $2$ (If the edges on both sides of the vertex were added back in) It can stay the same (if one edge was removed and the other was added back in) or it can decrease by two (if both edges where removed). We then proceed to making $a_3$ and $b_3$ both odd by using the same approach as for $a_2$ and $b_2$. We then make $a_4$ and $b_4$ odd and so on until we make $a_k$ and $b_k$ both odd. When we do this we will be finished. $\endgroup$
    – Asinomas
    Jun 28 '15 at 17:40
  • 1
    $\begingroup$ Yes, I've gotten it now. You should add this argument to your answer. Thanks a lot for your help. $\endgroup$
    – rah4927
    Jun 28 '15 at 17:52
3
$\begingroup$

So, to simplify things, assume we have a tree with an even number of vertices.

I think that this idea has potential! Here is a way to proceed and prove the assertion at hand:

If, in the resulting tree, each vertex has odd degree, then we are done. Otherwise, there must be some vertex, let us call it $v$, for which deg$(v)$ is even. In considering the even number of strands emanating from $v$, we wonder:

Q: Can each of the evenly many strands - discounting $v$ - contain an odd number of vertices?

The answer to the above question is no: If each strand had an odd number of vertices, then adding up the vertex count across the even number of strands, we would end up with an even sum; but, when we then re-included $v$, the total number of vertices would be odd, which cannot be the case since our tree has, by assumption, an even number of vertices.

Thus, (at least) one strand emanating from $v$ has an even vertex count. Let us remove an edge connecting one such strand to $v$; in the process, we not only ensure that deg$(v)$ is (for the moment) odd, but we also reduce the problem from a single tree with an even number of vertices to two trees each with even numbers of vertices.

We may now repeat our approach in these two trees, each of which has an even vertex count that is strictly smaller than the initial tree's, and, by iterating, we ultimately arrive at a graph for which each vertex has odd degree as desired. QED.

$\endgroup$
3
  • 1
    $\begingroup$ Whoa, this is quite a nice solution using the spanning tree idea. Thanks. $\endgroup$
    – rah4927
    Mar 27 '18 at 7:22
  • 1
    $\begingroup$ @rah4927 You're welcome! I solved this as a challenge problem in a graph theory course back in 2011, and when googling for its source stumbled upon the post here. Still unsure of the proposition's provenance, but glad you enjoyed this approach! $\endgroup$ Mar 27 '18 at 7:27
  • $\begingroup$ @rah4927 PS: The solution here is by algorithm. A slight modification is to assume you have a counterexample with vertex count minimal; applying the approach above (splitting into two trees) yields a counterexample to the minimality. $$ $$ As this uses the Well Ordering Principle, it is also (essentially) a proof by induction. $\endgroup$ Mar 27 '18 at 7:36
2
$\begingroup$

This is a linear algebra problem. Let $M$ be the incidence matrix of $G$. (Let $G$ have $n$ vertices and $m$ edges; then $M$ has $m$ rows and $n$ columns; the row corresponding to an edge has two $1$'s corresponding to the endpoints of the edge.) We seek an $m$-long vector $\mathbf{x}$, whose entries are $0$'s and $1$'s, such that $$\mathbf{x} M = \mathbf{j}\ \mathrm{mod\ }2,$$ where $\mathbf{j}=(1,1,\ldots,1)\in\mathbb{F}_2^n$; the entries of $\mathbf{x}$ tell us which edges to select. In other words, the problem is equivalent to asking whether $\mathbf{j}$ is in the rowspace $rs(M)$ of $M$, working over the $2$-element field $\mathbb{F}_2$.

I claim that $rs(M)$ consists precisely of the $(n-1)$-dimensional subspace of $\mathbb{F}_2^n$ consisting of vectors with even row sum. Clearly $rs(M)$ is contained in this subspace (since each row of $M$ has row sum $2$). We have $\dim rs(M)=n-1$ since $G$ is connected: the edges of any spanning tree $T$ of $G$ are linearly independent.

Finally, since $n$ is even, the vector $\mathbf{j}$ has even row sum, and therefore is in $rs(M)$, as required.

$\endgroup$
2
  • $\begingroup$ Thanks for taking the time to answer this question. However, I am not familiar with the ties of graph theory with linear algebra(though I have heard of it often). Can you suggest a source from where I can learn about how graph theory links with linear algebra? I know very little linear algebra, but am willing to expand my knowledge because I am fond of it. $\endgroup$
    – rah4927
    Jun 28 '15 at 21:03
  • 1
    $\begingroup$ The most important thing to do is learn linear algebra well. Once you have that under your belt, you'll see that it applies everywhere (and the graph theory connections will be obvious.) A math.SE discussion of good sources can be found at math.stackexchange.com/questions/4335/…. $\endgroup$
    – Tad
    Jun 29 '15 at 1:06
2
$\begingroup$

This is really an addendum to Gamamal’s excellent answer, but it’s a bit long for a comment.

Gamamal’s second argument can also be phrased as a downward induction. The result is clearly true for $K_{2n}$. Suppose that it’s true for some connected graph $G$ on $2n$ vertices, and let $E$ be a set of edges of $G$ such that each vertex of $G$ is incident with an odd number of edges in $E$. Suppose that removing the edge $\{u,v\}$ from $G$ leaves a connected graph $H$. If $\{u,v\}\notin E$, $E$ still witnesses the truth of the result for $H$. Otherwise, since $H$ is connected, let $u=v_0,v_1,\ldots,v_k=v$ be a path in $H$. Let $$P=\big\{\{v_i,v_{i+1}\}:i=0,\ldots,k-1\big\}\;,$$ and let $E'=E\mathbin{\triangle}P$, where $\triangle$ denotes symmetric difference. (In other words, if an edge on the path from $u$ to $v$ is in $E$, remove it, and if it’s not, add it.) For any vertex $w$ let $e(w)$ and $e'(w)$ be the numbers of edges of $E$ and $E'$, respectively, incident at $w$. Then it’s easy to see that the absolute change $|e'(w)-e(w)|$ is

  • $1$ if $w\in\{u,v\}$;
  • $0$ or $2$ if $w\in\{v_1,\ldots,v_{k-1}\}$; and
  • $0$ otherwise.

It follows that every vertex of $H$ is incident with an odd number of edges of $E'$.

Since every connected graph on $2n$ vertices can be obtained in this way, the result is proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.