4
$\begingroup$

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?

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

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.