For any simple, undirected graph $G=(V,E)$, we denote by $\chi(G)$ the smallest cardinal $\kappa$ such that there is a coloring $c:V \to \kappa$.
We say that $v\neq w\in V$ are incompatible if $\{v,w\}\notin E$, and for any coloring $c: V\to \chi(G)$ we have $c(v) \neq c(w)$.
It is easy to see that if $v\neq w\in V$ are incompatible, they must lie in the same connected component of $G$.
What is an example of a graph containing an incompatible pair of vertices?
If $R$ is a poset, then a function $C:R\rightarrow R$ is said to be a closure operator if $r\leq C(r)=C(C(r))$ and $(r\leq s)\rightarrow(C(r)\leq C(s))$ whenever $r,s\in R$. We say that a subset $C\subseteq R$ is a closure system if for all $r\in R$, there is a least $s\in C$ where $r\leq s$. If $R$ is a complete lattice, then $C\subseteq R$ is a closure system if and only if $C$ is closed under arbitrary greatest lower bounds including the empty greatest lower bound. The closure operators and closure systems on a poset are in a one-to-one correspondence. If $C$ is a closure system, then let $C^{*}:R\rightarrow R$ be the mapping where if $r\in C$, then $C^{*}(r)$ is the least element $s$ in $C$ with $r\leq s$. Then $C^{*}$ is a closure operator. Similarly, if $C$ is a closure operator, then define $C^{*}=\{r\in R\mid r=C(r)\}$. Then $C^{*}$ is a closure system. Furthermore, if $C$ is a closure operator or closure system, then $C=(C^{*})^{*}$.
Suppose that $R,S$ are posets. Then a pair of mappings $f:R\rightarrow S,g:S\rightarrow R$ is said to be a Galois connection if $s\leq f(r)\leftrightarrow r\leq g(s)$. If $f:R\rightarrow S,g:S\rightarrow R$ is a Galois connection, then the functions $f\circ g,g\circ f$ are closure operators. Furthermore, the maps $f,g$ restrict to order reversing inverse bijections between the closure systems $(f\circ g)^{*},(g\circ f)^{*}$.
Suppose that $X,Y$ are sets. Let $R\subseteq X\times Y$ be a relation. Then define functions $F:P(X)\rightarrow P(Y),G:P(Y)\rightarrow P(X)$ by letting $F(A)=\{y\in Y\mid\forall x\in A,(x,y)\in R\}$ and $G(B)=\{x\in X\mid\forall y\in B,(x,y)\in R\}$. Then the functions $F,G$ form a Galois connection.
Let $\lambda$ be a cardinal, and let $V$ be a vertex set. Then define a relation $R_{\lambda,V}\subseteq[V]^{2}\times^{V}\lambda$ where if $u,v\in V,u\neq v$ and $f:V\rightarrow\lambda$ is a function, then $\{u,v\},f)\in R_{\lambda,V}$ if and only if $f(u)\neq f(v)$. Then from this relation, we define a Galois connection $F_{\lambda,V}:P([V]^{2})\rightarrow P(^{V}\lambda),G_{\lambda,V}:P(^{V}\lambda)\rightarrow P([V]^{2})$ the standard way by setting $F_{\lambda,V}(R)=\{s\in^{V}\lambda\mid\forall r\in R,(r,s)\in R_{\lambda,V}\}$ and $G_{\lambda,V}(S)=\{r\in[V]^{2}\mid\forall s\in S,(r,s)\in R_{\lambda,V}\}$.
Define closure operators $C_{\lambda,V}:P([V]^{2})\rightarrow P([V]^{2}),D_{\lambda,V}:P(^{V}\lambda)\rightarrow P(^{V}\lambda)$ by letting $C_{\lambda,V}=G_{\lambda,V}\circ F_{\lambda,V},D_{\lambda,V}=F_{\lambda,V}\circ G_{\lambda,V}$.
If $G=(V,E)$, then the following are equivalent:
$\chi_{G}\leq\lambda$.
$F_{\lambda,V}(E)\neq\emptyset$.
$C_{\lambda,V}(E)\neq[V]^{2}$.
We observe that if $\lambda,\mu$ are cardinals with $\lambda\leq\mu$, then $C_{\mu,V}(E)\subseteq C_{\lambda,V}(E)$.
In particular, if $\lambda$ is a cardinal and $F_{\lambda,V}(E)\neq\emptyset$, then every edge in $C_{\lambda,V}(E)\setminus E$ is an incompatible edge. In particular, the graph $(V,E)$ has an incompatible edge if and only if $E$ is non-closed and non-dense.
Finite chromatic number examples
If $(V,E)$ is a connected bipartite graph with bipartition $A,B$, then $C_{2,V}(E)=\{\{a,b\}\mid a\in A,b\in B\}$. Connected incomplete bipartite graphs therefore have incompatible edges.
More generally, as was mentioned by Tony Huynh in the comments, we say that a graph $G=(V,E)$ is uniquely colorable with $k$ colors if it is not colorable with $k-1$ colors and where there is only one coloring $f:V\rightarrow k$ up to permutations (i.e. if $f,g:V\rightarrow k$ are colorings, then there is a permutation $h\in S_{k}$ with $g=h\circ f$). Every complete graph is uniquely colorable. Furthermore, one can easily construct new uniquely colorable graphs from old uniquely colorable graphs. Suppose that $(V,E)$ is a uniquely colorable graph with $k$-colors. Let $f:V\rightarrow k$ be the unique (up-to-permutation) coloring of $(V,E)$. Then let $v$ be a vertex with $v\not\in V$. Then let $v_{1},\dots,v_{k}$ be vertices where $f(v_{1}),\dots,f(v_{k})$ are distinct. Then $(V\cup\{v\},E\cup\{\{v,v_{i}\}\mid 1\leq i\leq k\})$ is also uniquely colorable. In particular, every k-tree is uniquely colorable with k colors.
If $(V,E)$ is a uniquely colorable graph with $k$ colors, and $f:V\rightarrow k$ is the unique coloring, then whenever $\{u,v\}\not\in E$ and $f(u)\neq f(v)$, the edge $\{u,v\}$ is incompatible with $(V,E)$. In particular, if $$|E|<|V|\cdot(|V|-1)/2-\sum_{i=0}^{k-1}|f^{-1}[\{i\}]|\cdot(|f^{-1}[\{i\}]|-1)/2,$$ then there is some edge $\{u,v\}$ incompatible with $(V,E)$.
Deletion-contraction
There is a deletion-contraction formula for the number of $k$-colorings of a graph, and this deletion-contraction formula applies for infinite graphs as well with infinitely many colorings.
Suppose that $G=(V,E)$ is a graph. If $\simeq$ is an equivalence relation on $V$, then let $G/\simeq$ denote the graph with vertex set $V/\simeq$ and with edge set $E/\simeq=\{\{[u],[v]\}\mid\{u,v\}\in E,u\not\simeq v\}$. If $\{u,v\}$ is a pair, then let $G/\{u,v\}$ denote the graph $G/\simeq$ where $x\simeq y$ if and only if $x=y$ or $\{x,y\}=\{u,v\}$.
If $(V,E)$ is a graph where $u,v,\in V,u\neq v,\{u,v\}\not\in E$, then by using the same notation as before, we define a function $$L:F_{k,V}(E\cup\{\{u,v\}\})\cup F_{k,V/\{u,v\}}(E/\{u,v\})\rightarrow F_{\lambda,V}(E)$$ by letting $L(f)=f$ whenever $f\in F_{k,V}(E\cup\{\{u,v\}\})$ and $L(f)=f\circ\pi$ where $\pi:V\rightarrow V/\{u,v\}$ is the quotient mapping.
Therefore, $F_{k,V}(E\cup\{\{u,v\}\})=F_{k,V}(E)$ if and only if $F_{k,V/\{u,v\}}(E/\{u,v\})=\emptyset$. In particular, if $\{u,v\}\in[V]^{2}\setminus E$, then $\{u,v\}$ is an incompatible edge for $(V,E)$ if and only if $$\chi(G/\{u,v\})>\chi(G).$$
infinite chromatic topology
Suppose that $\lambda$ is an infinite cardinal. Let $\text{pc}(\lambda)$ be the least cardinal with $\lambda^{\text{pc}(\lambda)}>\lambda$.
Proposition: $C_{\lambda,V}^{*}$ is a topological closure system. In the corresponding topology, the union of less than $\text{pc}(\lambda)$ many closed sets is closed, and the intersection of less than $\text{pc}(\lambda)$ many open sets is open.
If $P$ is a partition of a set $V$, then let $U_{P}=\{\{u,v\}\mid u\neq v,u=v(P)\}$. In the $C_{\lambda,V}$-topology, the basic open sets are precisely the sets of the form $U_{P}$ where $|P|\leq\lambda$.
If $\lambda=|V|$, then the $C_{\lambda,V}$-topology is discrete.
Proposition: A non-empty subset $A\subseteq[V]^{2}$ is open in the $C_{\lambda,V}$-topology if and only if $U_{P}\subseteq A$ for some partition $P$ with $|P|\leq\lambda$.
Proof: The direction $\rightarrow$ has already been established. For the direction, $\leftarrow$, suppose that $P$ is a partition of $V$ into at most $\lambda$ many sets. Then we shall show that $U_{P}\cup\{\{p,q\}\}$ is open for each pair $p,q$ with $p\neq q$. The case where $p=q(P)$ is trivial, so assume that $p\neq q(P).$
Let $$Q=(\{\{p,q\}\}\cup\{R\setminus\{p,q\}|R\in P\})\setminus\{\emptyset\}.$$ Then $$U_{P}\cup\{\{p,q\}\}=U_{P}\cup U_{Q}.$$
Q.E.D.
Therefore, if $A\subseteq[V]^{2}$, then either $A$ is dense in the $C_{\lambda,V}$ topology or $A$ is closed in the $C_{\lambda,V}$ topology. Therefore, for each graph $(V,E)$, we know that $C_{\lambda,V}(E)=[V]^{2}$ or $V_{\lambda,V}(E)=E$. Therefore, the graph $(V,E)$ can never have an incompatible edge whenever $(V,E)$ has infinite chromatic number.
You can also argue that if $G$ has infinite chromatic number, then $G$ cannot have an incompatible edge by using the facts that that $\chi(G/\{u,v\})\leq\chi(G)+2$ but in order for $\{u,v\}$ to be incompatible, we must have $\chi(G/\{u,v\})>\chi(G)$.
