Return to Answer

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 vertes $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 $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.

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.

Remark. A minimally separating graph is triangle-free.

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.

 
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.

 
Remark. A minimally separating graph is triangle-free.

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

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

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.