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?



Minimally separating graphs
Yes, every separating graph has a spanning subgraph which is minimally separating. The proof uses the same idea as the [Banakh–Petrov theorem](https://mathoverflow.net/questions/324504/graphs-with-minimum-degree-deltag-lt-aleph-0).


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.


