**Motivation.** At a recent gathering of co-workers, somebody said that he thinks that of all the people present that he knows, about half are happy with the current COVID19 measures, and the other half are not. Which made me put this into a graph question: Given a finite, simple, undirected graph $G = (V,E)$, we say that G is "perfectly balanceable" if there is a set $C\subseteq V$ such that for every $v\in V$, exactly half of its neighbors are in $C$. Clearly, if a vertex has an odd number of neighbors, the graph cannot be perfectly balanceable. So, below I try to introduce a "discrepancy measure" that indicates how far a graph is from being perfectly balanceable.


**Formal version.** Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$, let $N(v)=\{w\in V: \{v,w\}\in E\}$. For $v\in V$ and $C\subseteq V$ let the *discrepancy* of $v$ with respect to $C$ be $$\text{d}\_C(v) = \big|\#\big(N(v) \cap C\big) - \#\big(N(v) \cap(V\setminus C)\big)\big|\;,$$
where $\#(\cdot)$ denotes the size of a (finite) set. The *maximal discrepancy* of any vertex with respect to $C$ is denoted by $$\text{md}\_G(C) = \max\{\text{d}\_C(v): v\in V\}.$$
Clearly, we have $\text{md}\_G(C) = \text{md}\_G(V\setminus C)$ for all $C\subseteq V$. The *overall discrepancy* of $G$ finally is defined by $$\text{discr}(G) = \min\{\text{md}\_G(C):C\subseteq V\}.$$


For example, it is not hard to see chat $\text{discr}(C\_4) = 0$ for the circle on $4$ vertices: If the circle is $0 - 1 - 2 - 3 - 0$, take $C = \{0,1\}$ for getting $\text{md}\_{C\_4}(C) = 0$ and therefore $\text{discr}(C\_4) = 0$. On the other hand, for any graph $G$ with a vertex $v$ such that $N(v)$ has an odd number of elements, we have $\text{discr}(G) > 0$.


**Question.** Given a positive integer $n>0$, is there a graph $G=(V,E)$ such that $\text{discr}(G) = n$?



Discrepancy number of a graph
Yes, there is such a graph. Let $A = \{1,\dots,2n\}$, let $B = \{b \subseteq A \colon |b|=n\}$, and let $G$ be a graph with vertex set $A \uplus B$ and an edge between $a\in A$ and $b\in B$ if $a \in b$.


For any set $C$ there are either $n$ vertices in $A \cap C$ or $n$ vertices in $A\setminus C$, and thus there is a vertex $b \in B$ with $d\_C(b) = n$.


