I've just begun studying graph theory and I have some difficulty with this problem. Could you tell me how to go about solving it?

In a graph $G$ all vertices have degrees $\le 3$. Show that we can color its vertices in two colors so that in $G$ there exists no one-color path, whose length is $3$.

And a similar one. There's this quite popular lemma that if in a graph all vertices have degrees $\ge d$, then in this graph there's a path whose length is $d$. In all proofs I've seen so far it only says that since minimal degree of these vertices is $d$, then there exist some vertices whose degree is $d$, and so all others must have degrees greater than $d$. I have no idea how to get path length from this. Could you help me with that, too?


1 Answer 1


EEDDIITT: Let $C=\{0,1\}^V$ be the set of 2-colourings $f\colon V\to\{0,1\}$. Any connected component of $G$ that consists of an isolated vertex or of two vertices joined by an edge, can clearly be ignored. Thus we may assume wlog. that $\rho(a)\ge1$ for all vertices $a$ and $\rho(a)\ge2\lor \rho(b)\ge2$ for all edges $ab$. For $f\in C$ and $S\subseteq V$, let $$ f_S(v)=\begin{cases}1-f(v)&\text{if }v\in S\\f(v)&\text{if }v\notin S\end{cases}$$ be the colouring obtained by flipping the colour for all vertices in $S$. For $f\in C$ and $v\in V$ and $n\in\mathbb N$, let $S_n(f)$ be the set of monochromatic length $n$ paths, i.e. $$ S_n(f)=\left\{(v_0,\ldots,v_n)\in V^{n+1}\mid \forall 0< i\le n\colon\ v_{i-1}v_{i}\in E, f(v_i)=f(v_0), i=n\lor v_{i+1}\ne v_{i-1}\right\}.$$ Let $$N=\min_{f\in C}|S_3(f)|,$$ $$M=\min_{f\in C, |S_3(f)|=N} |S_1(f)|$$ and fix a colouring $f\in C$ with $|S_3(f)|=N$, $|S_1(f)|=M$.

Lemma 1: Every vertex has a neighbour of different colour. Or: Every vertex is incident with a bichromatic edge.

Proof: Assume $a\in V$ has only vertices of the same colour. Using the fact that $\rho(a)\ge1$, let $b$ be a neighbour of $a$. Let $g=f_{\{a\}}$. Then $S_3(g)\subseteq S_3(f)$ and $S_1(g)\subsetneq S_1(f)$ because any difference can only come from paths containing $a$ and in fact $ab$ is no longer monochromatic with colouring $g$. Then $|S_3(g)|\le N$, $|S_1(g)|<M$ contradicts minimality of $f$. $_\square$

Lemma 2: If $ab$ is an edge with $f(a)\ne f(b)$ then $a$ has a neighbour $c\ne b$ with $f(c)\ne f(a)$ or $b$ has a neighbour $c\ne a$ with $f(c)\ne f(b)$. Or: At least one endpoint of a bichromatic edge is incident with another bichromatic edge.

Proof: Assume otherwise and let $g=f_{\{a,b\}}$. Then $S_3(g)\subseteq S_3(f)$ and $S_1(g)\subsetneq S_1(f)$ (for the latter making use of $\rho(a)\ge 2\lor \rho(b)\ge 2$), again leading to a contradiction to the minimality of $f$. $_\square$

Theorem: $N=0$.

Proof: Assume otherwise and let $(a,b,c,d)\in S_3(f)$ (note that possibly $d=a$, but $a,b,c$ are distinct). By lemma 1, $b$ has a neighbour $x$ with $f(x)\ne f(b)$. By lemma 2 applied to $bx$, $x$ has at least one neighbour $y\ne b$ with $f(y)\ne f(x)$, hence at most one neighbour $z$ with $f(z)=f(x)$. Let $g=f_{\{b\}}$. Then from the edges $ba$, $bc$ and $bx$ we learn that $|S_1(g)|=|S_1(f)|-1$, hence $|S_3(g)|>|S_3(f)|$ by minimality of $f$. Since $(a,b,c,d), (d,c,b,a)\in S_3(f)\setminus S_3(g)$, there must be at least three paths in $S_3(g)\setminus S_3(f)$. In fact, paths always come in pairs (with their reverses), hence there must be at least four such paths. Since $b$ can only occur as start- or endpoint, at least two paths must start at $b$ (and two end there). These necessarily have the forms $(b,x,z,v)$ and $(b,x,z,w)$ with $v\ne w$. By definition of $S_3(g)$, vertices $b,x,z$ are distinct. Then $f(z)=g(z)=g(b)\ne f(b)$ and since $z\ne x$, $z$ is not a neighbour of $b$. Consequently, $v\ne b$ and $w\ne b$. Therefore $b\notin\{x,z,v,w\}$ and $g(x)=g(z)=g(v)=g(w)$ implies $f(x)=f(z)=f(v)=f(w)$, contradicting lemma 1 (applied to $z$). $_\square$

For the second problem, what you write about the proofs makes little sense. However: Let $v_0v_1\ldots v_r$ be a path of maximal length $r$. Then there is no vertex $v_{r+1}$ adjacent to $v_r$ such that $v_0v_1\ldots v_rv_{r+1}$ is a path. That is: All edges incident with $v_r$ are among the $r$ edges $v_0v_1, v_1v_2, \ldots, v_{r-1}v_r$. This implies $r\ge d$.

  • $\begingroup$ I'm sorry. I don't understand the first one. You say that in the beginning $a_1, a_2, x_1, y_1$ have the same color. Then we change $a_2$'s color (the rest stays the same, doesn't it?) and now $a_3$ is the only neighbour of $a_1$ having the same colour. Then how can $a_2, a_3, x_2, y_2$ be monochromatic? $\endgroup$
    – Hagrid
    Commented Jan 13, 2013 at 19:26
  • $\begingroup$ By minimality, there must be a new such path and it must involve $a_2$ and it cannot involve the neighbours $a_1$ and $x_1$ of $a_2$, hence it must start $a_2a_3\ldots$. $\endgroup$ Commented Jan 13, 2013 at 20:54
  • $\begingroup$ Meanwhile, I've generously restructured the first part to avoid my originally intended recursive construction and lay more weight on the idea of a "minimal counterexample" (which is just induction in disguise). Unfortunately, this is way more explicit than it should be for a homework hint ... $\endgroup$ Commented Jan 14, 2013 at 18:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .