ZoĆ© Christoff edited section_Unanimity_and_2_colorability__.tex  about 8 years ago

Commit id: a1f43e3324b60e37683c04061430d1087407b432

deletions | additions      

       

\item[] For all $p\in\Atoms$, $G_p$ is not $2$-colorable.   \end{lemma}  \begin{proof}  Let $p\in\Atoms$ and $G_p$ be not $2$-colorable. This means that for some connected set of nodes $S\subseteq\N$ with diameter $k$ in $G_p$, there is a cycle of length $c$ for $c$ odd. Let $O$ be an arbitrary opinion profile. Since $k$ is odd, there exist $i,j\in S$ such that $j\in R_p(i)$ and $O_i(p)=O_j(p).$ By definition of UP, this implies that $O_i(p)$ is stable, and that all agents with distance $\seq $\leq  k$ will be stable after at most $k$ steps. The lemma above gives the other direction. \end{proof}  \begin{theorem}