Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Prove that if G is a connected graph that is not an odd cycle, then it has an edge 2-coloring such that every vertex with degree at least two is adjacent to edges of both colors.
My own idea was to prove it by induction on the number of vertices, but the problem is that if we omit a vertex that all of its neighbors have degree two, then we might face a problem to complete the induction.
By a good coloring of a graph $G$ I mean a $2$-coloring of the edges with colors red and blue such that every vertex of degree at least $2$ is incident with a red edge and a blue edge.
Lemma. Let $G$ be a connected graph which is not an odd cycle. If $G$ has at most one vertex of degree different from $2$, then $G$ has a good coloring.
Proof. If all vertices of $G$ have degree $2$, then $G$ is an even cycle. If $G$ has just one vertex $v$ of degree different from $2$, then either $G=K_1$, or else $G$ consists of two or more cycles glued together at one vertex. (Note that $G$ is Eulerian, and consider the cycles traversed by an Euler circuit between successive visits to $v$.) In all these cases the existence of a good coloring is easily verified.
Theorem. Every connected graph which is not an odd cycle has a good coloring.
Proof. We use induction on the size of the graph, i.e., the number of edges. Let $G$ be a connected graph which is not an odd cycle, and assume that the theorem holds for all smaller graphs.
By the lemma, we may assume that $G$ has two distinct vertices, $u$ and $v$, whose degrees are different from $2$. Let $P$ be a path from $u$ to $v$. Color the edges of $P$ alternately red and blue.
Now consider the connected components of $G-E(P)$. Give each component which is not an odd cycle a good coloring, which exists by the inductive hypothesis. However, if any component $C$ of $G-E(P)$ is an odd cycle, then choose a vertex $w\in V(C)\cap V(P)$, and color the edges of $C$ alternately red and blue, except that the two edges incident with $w$ shall have the same color, and if $w$ happens to be an end vertex of $P$, that color shall be different from the color of the edge of $P$ which is incident with $w$.
It is easy to see that this is a good coloring of $G$.
I think it's much cleaner to prove it by induction on the number of edges without specifying a number of vertices. Note that the result is trivial if the graph has less than $2$ edges. Note, furthermore, that the result is obvious for connected graphs with maximal degree at most two that are not odd cycles since these are either even cycles or line segments (i.e. graphs of the form $[k]$).
A little less clear, the result is also immediately true if $G$ has a unique vertex $v$ of degree at least $3$. Indeed, in this case, let $E_v$ denote the set of edges adjacent to $v$ .Then, $\tilde{G}=(V,E\setminus E_v )$ is a disjoint collection $\{\tilde{G}_j\}_{1\leq j\leq J}$ such that each $\tilde{G}_j$ is either an isolated vertex or a line segment with end points $v_j$ and $w_j$. Note that $J\geq 2$ by assumption. For each $j$ such that $\tilde{G}_j$ is not an isolated vertex, pick an edge 2-colouring $\mathcal{C}_j$ of the edges in $\{\tilde{G}_j\}_{1\leq j\leq J}$ satisfying our assumption. Then, since $v_j$ and $w_j$ both have degree at most two in $G$ and at least one of them is a neighbour of $v$, there is a unique way to extend $\mathcal{C}_j$ to edges between $v$ and $\tilde{G}_j$ such that $v_j$ and $w_j$ have neighbouring edges of both colours if they have degree two. For $j$ such that $\tilde{G}_j$ is an isolated vertex, we can of course colour its edge to $v$ freely.
Now, since we can choose the $\mathcal{C}_j$ independently and there are at least two such colourings, we can glue them all together and obtain an edge 2-colouring of $G$ satisfying our assumption.
Hence, assume the result is proven for graphs with at most $n$ edges and assume that $G=(V,E)$ is connected a graph with $n+1$ edges that is not an odd cycle, and also has two vertices $v$ and $w$ with degree at least $3$. Since, $G$ is connected, there exists a path $(\gamma_j)_{1\leq j\leq J}$ such that $\gamma_1=v$ and $\gamma_J=w$. Furthermore, by replacing $w$ with the first $\gamma_{J'}$ with degree at least three, we can assume without loss of generality that $\gamma_j$ has degree exactly two for $2\leq j\leq J-1$.
Let $E_{\gamma}$ be the set of edges that $\gamma$ uses and observe $\tilde{G}_1=(V,E\setminus E_{\gamma})$ and $\tilde{G}_2=(V,E_{\gamma})$. Then, $\tilde{G}_2$ is a union of isolated vertices and a line segment, so it admits an edge two-colouring satisfying our assumptions where we can freely choose the colour of the unique edge in $\tilde{G}_2$ adjacent to $v$. Label such a colouring $\mathcal{C}_2$. Now, $\tilde{G}_1$ might be a union of isolated vertices and an odd cycle, but in this case $\tilde{G}_1$ admits an edge 2-colouring such that all vertices except for $v$ has a neighbouring edge of both colours. Otherwise, simply apply the induction hypothesis to the unique component of $\tilde{G}_1$ that does not consist of an isolated vertex (remember, the degree of each $\gamma_j$ is $2$ for $2\leq j \leq J-1$). Whatever the case, label the colouring $\mathcal{C}_1$.
Thus, if we set $$ \mathcal{C}(e)=\begin{cases} \mathcal{C}_1(e) & e\in E\setminus E_{\gamma} \\ \mathcal{C}_2(e) & e\in E_{\gamma}\end{cases}, $$ we obtain the desired since the only possible problem could arise at $v$, but the colour of the edges adjacent to $v$ in $E_{\gamma}$ and $E\setminus E_{\gamma}$ can be chosen independently.
