# Minimally separating graphs

We say that a simple, undirected graph $$G=(V,E)$$ is separating if for all $$x\neq y\in V$$ there are $$e_x,e_y\in E$$ such that $$x\in e_x$$ and $$y\in e_y$$, and $$e_x\cap e_y = \varnothing$$. We say $$G$$ is minimally separating if it is separating and for all $$E'\subseteq E$$ with $$E'\neq E$$ we have that $$(V,E')$$ is no longer separating.

Here is an example: consider an infinite disjoint union of squares; formally, set $$V=\omega$$, and let $$E = \big\{\{n,n+1\}: (n\in\omega) \land(\forall a\in \omega(4a+3 \neq n))\big\}\cup\big\{\{4n,4n+3\}:n\in \omega\big\}.$$ Then $$G=(V,E)$$ is minimally separating.

Question. If $$G=(V,E)$$ is a separating graph, is there $$E_1\subseteq E$$ such that $$(V,E_1)$$ is minimally separating?

• Thanks for the pointer to that question, it does seem related to my question – Dominic van der Zypen Oct 6 '20 at 14:33

Yes, every separating graph has a spanning subgraph which is minimally separating. The proof uses the same idea as the Banakh–Petrov theorem.

Let $$G=(V,E)$$ be a separating graph. I will write $$N(x)$$ and $$d(x)=|N(x)|$$ for the neighborhood and the degree of a vertex $$x$$ in $$G$$, and I will write $$N_1(x)$$ and $$d_1(x)$$ for the neighborhood and the degree of $$x$$ in the spanning subgraph $$G_1=(V,E_1)$$ to be constructed in Step 1.

Step 1. Let $$G_1=(V,E_1)$$ be a maximal spanning subgraph of $$G$$ with maximum degree $$\Delta(G_1)\le3$$, and let $$W=\{x\in V:d_1(x)=3\}$$; thus every edge $$e\in E\setminus E_1$$ has at least one endpoint in $$W$$.

Step 2. We will now construct a set $$E_2\subseteq E\setminus E_1$$ such that $$G_{1,2}=(V,E_1\cup E_2)$$ is a separating graph, and $$G_{1,2}-e$$ is non-separating for each $$e\in E_2$$. In order to make $$G_1$$ a separating graph by adding new edges, we only have to worry about vertices $$x$$ such that either $$d_1(x)\lt2$$ or else $$d_1(x)=2$$ and $$x$$ is in a triangle which has at least two such vertices. We consider several cases. The locution "draw a new edge" shall mean "choose an edge $$e\in E\setminus E_1$$ and add it to $$E_2$$"; the set $$E_2$$ shall consist of all the new edges chosen in Step 2.

Case I. $$d_1(x)=0$$.

Draw two new edges joining $$x$$ to vertices in $$W$$.

Case II. $$d_1(x)=d_1(y)=1$$ and $$xy\in E_1$$.

Draw two new edges joining $$x$$ and $$y$$ to two distinct vertices in $$W$$.

Case III. $$d_1(x)=1$$ and there are vertices $$y\in V\setminus W$$ and $$z\in W$$ such that $$xy,yz\in E_1$$.

If possible, draw a new edge joining $$x$$ to a vertex in $$W$$ distinct from $$z$$. If that's not possible then draw two new edges, joining $$x$$ to $$z$$ and joining $$y$$ to another vertex in $$W$$.

Case IV. $$d_1(x)=1$$ and neither Case II nor Case III applies.

Draw a new edge joining $$x$$ to a vertex in $$W$$.

Case V. $$d_1(x)=d_1(y)=2$$ and there is a vertex $$z\in W$$ such that $$xy,xz,yz\in E_1$$.

Draw a new edge joining either $$x$$ or $$y$$ to another vertex in $$W$$.

Case VI. $$d_1(x)=d_1(y)=d_1(z)=2$$ and $$xy,xz,yz\in E_1$$.

Draw two new edges joining two distinct vertices in $$\{x,y,z\}$$ to vertices in $$W$$, not necessarily distinct.

Let $$E_2$$ be the subset of $$E\setminus E_1$$ consisting of all the new edges from Step 2. It is easy to see that the graph $$G_{1,2}=(V,E_1\cup E_2)$$ is separating, and for each $$e\in E_2$$ the graph $$G_{1,2}-e$$ is non-separating.

Step 3. We want to find a minimal set $$F\subseteq E_1\cup E_2$$ such that $$(V,F)$$ is a separating graph; equivalently, a maximal set $$S\subseteq E_1\cup E_2$$ such that $$(V,(E_1\cup E_2)\setminus S)$$ is a separating graph.

Call a set $$S\subseteq E_1\cup E_2$$ good if $$(V,(E_1\cup E_2)\setminus S)$$ is a separating graph, bad if $$(V,(E_1\cup E_2)\setminus S)$$ is not a separating graph. Plainly, a subset of a good set is good. We want to find a maximal good set.

Claim. Every bad set $$S\subseteq E_1\cup E_2$$ contains a finite bad set.

Proof of Claim. Suppose $$S$$ is a bad set. Since $$\{e\}$$ is bad whenever $$e\in E_2$$, we may assume that $$S\subseteq E_1$$. By the definition of a separating graph, there are vertices $$x,y\in V$$ such that $$S$$ contains a bad subset $$S_0$$ consisting of edges incident with $$x$$ or $$y$$, that is, $$S_0\subseteq N_1(x)\cup N_1(y)$$. But then $$S_0$$ is finite, since the graph $$G_1$$ is locally finite, being subcubic.

It follows from the Claim and Zorn's lemma that there is a maximal good set $$S\subseteq E_1\cup E_2$$, whence $$(V,(E_1\cup E_2)\setminus S)$$ is a spanning subgraph of $$G$$ which is minimally separating.

Remark. A minimally separating graph is triangle-free.

Suppose $$G$$ is a separating graph, and suppose $$G$$ contains a triangle with vertices $$x,y,z$$. At least two of the three vertices, say $$x$$ and $$y$$, have degree at least $$3$$. If $$G-xy$$ is not a separating graph, then there must be a vertex of degree $$2$$ which is adjacent to $$x$$ and $$z$$ or to $$y$$ and $$z$$; let's say $$N(w)=\{x,z\}$$. But now it's easy to see that $$G-xz$$ is a separating graph, so $$G$$ is not minimally separating.