Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
    
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? –  Hagrid Jan 13 '13 at 19:26
    
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$. –  Hagen von Eitzen Jan 13 '13 at 20:54
    
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 ... –  Hagen von Eitzen Jan 14 '13 at 18:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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