# How to formally write a property of a specific coloring of a graph.

I have a doubt about how to write a statement in rigorous logical notation.

I have a graph whose nodes are partitioned in some subsets $V_1,...,V_k$ and I have a function $Z:V\rightarrow \mathbb N$ that assign a different and unique number to each subset. I want to formalize in logical notation the definition of $Z$. My first attempt is the following: $$\forall j \in [\ell], \ \forall u,v \ \in V_j : Z(u) = Z(v) , \ \mbox{ and } \ \forall i\neq j \in [\ell] , \forall v \in V_i \ , \forall u \in V_j \ : Z(v) \neq Z(u)$$ Is it right? My doubt is about the use of the colon, that as far as I know means "such that", but here I'm using it in the meaning of "then it holds" because sometimes I saw it being used in this way.

Another way to write it, based on the notation I've seen on some Computer Science books, could be: $$\forall j \in [\ell]\left[ u,v \ \in V_j \implies Z(u) = Z(v)\right] \ \mbox{ and } \ \forall i\neq j \in [\ell] \left[ v \in V_i \ , u \in V_j \ \implies Z(v) \neq Z(u)\right]$$ where the square parenthesis are used to specify what formula is quantified by the symbols before the parenthesis. Is this correct? If both are, are them equivalent and which one is better? Is there another way you can suggest?

-

I would not write it formally: that simply obscures the meaning. I would probably describe it in one of the following ways or some minor variant thereof.

1. $\big\{V_k:k\in[\ell]\big\}$ is a partition of $V$, $\varphi:[\ell]\to\Bbb N$ is an injection, and $Z:V\to\Bbb N$ is defined by setting $Z(v)=\varphi(k)$ if and only if $v\in V_k$.

2. $\big\{V_k:k\in[\ell]\big\}$ is a partition of $V$. For $u,v\in V$ write $u\sim v$ if and only if there is a $k\in[\ell]$ such that $u,v\in V_k$; clearly $\sim$ is an equivalence relation. Then $Z:V\to\Bbb N$ is a function such that $Z(u)=Z(v)$ if and only if $u\sim v$.

If you absolutely must describe this characteristic of $Z$ in formal symbolic terms:

$$\forall k\in[\ell]\,\forall u,v\in V_k\Big(Z(u)=Z(v)\Big)\land\forall i,k\in[\ell]\left(i\ne k\to\forall u\in V_i\,\forall v\in V_k\Big(Z(u)\ne Z(v)\Big)\right)$$

$$\forall i,k\in[\ell]\,\forall u\in V_i\,\forall v\in V_k\Big(Z(u)=Z(v)\leftrightarrow i=k\Big)$$
I think you meant $Z(u) = Z(v) \leftrightarrow i = k$ – roliu Jan 28 '13 at 19:59