Discrepancy number of a graph

Question

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

Answer 1

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