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$ Commented Oct 6, 2020 at 14:33

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .