# Graph minus a point has a separation

(It's wrong there is a separation even for for a graph with a basic Hamiltonian path.)

Let G(V,E) be a connected (no separation) directed graph, such that, $$S_x$$=V∖{x}, ∀x∈V is a subset of vertices of G. Then the induced subgraph G[$$S_x$$] is the graph whose vertex set is $$S_x$$ and whose edges set consists of all of the edges in E that have both endpoints in $$S_x$$.

Then a necessary condition (not sufficient see link Graph minus a point has at most 2 connected components for a counterexample) for a graph G(V,E) to have a Hamiltonian path (not necesarily a cycle) is that the induced subgraphs ∀x∈V, G[$$S_x$$] have at most 2 connected components.

Now, let G[$$S_x$$] have 2 disjoint nontrivial connected components, let's say that $$S_x$$ = $$A_x \cup B_x$$, then we say that:

$$E_{-}$$={$$(a,b) \in E: \forall a \in A_x \forall b \in B_x \ | \ (a,x) \in E, (x,b) \in E$$}

$$E_{+}$$={$$(b,a) \in E: \forall a \in A_x, \forall b \in B_x \ | \ (b,x) \in E, (x,a) \in E$$}

$$E_x$$={$$(y,z) \in E: \forall y,z \in V, y \neq x, z \neq x$$}

Then I want to either proof or find a counterexample of the following statement, if $$\forall x \in V$$ none of the graphs,

G(V\ {x}, $$E_x \cup E_{+}$$)

G(V\ {x}, $$E_x \cup E_{-}$$)

have a separation then G(V,E) has a Hamiltonian cycle.

(A separation of V are 2 disjoint nontrivial sets C and D, such that C $$\cup$$ D = V. I define a separation between two points in a graph G(V,E) $$x, y \in V$$ when I can't find a direct/undirect path from x to y in E) i.e.

$$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

Can't find a path from cities (1 and 2) to cities (3 and 4)

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

Can't find a path from city 1 to cities (2, 3 and 4)

notice that the power of those matrices M^2, M^3 preserve the zeroes, so it should be easy to find a separation (hopefully in Polynomial time).

• Start with an undirected graph G(V,E) (so that if it has a Hamiltonian path then the graph is connected sideways thus there can't be a separation of 2 cities) Jan 1, 2021 at 15:04
• Your two subgraphs of the form $(V \setminus \{x\}, ...)$ are ill-defined because you cannot have edges incident to $x$ when $x$ is not present in your graph. I suppose what you propose could be described as: Take some graph $G_0$ and pick some order $v_0, ..., v_{n}$ and define $G_i$ as the graph $G_0[\{v_i, ...., v_n\}]$. Then $G_0$, the initial graph, has a HP if $G_i$ has at most $i + 1$ components? Jan 1, 2021 at 15:40
• Also, your definition of "separation" doesn't make much sense to me as it stands, and I don't see how it relates to "separation between two points". Jan 1, 2021 at 15:57
• If you want to edit to make it more comprehensible go ahead. Jan 1, 2021 at 16:01
• I can't because I don't know what you mean to say in the first place. Jan 1, 2021 at 16:02

Consider the undirected graph obtained from a cycle graph $$C_n$$ (with $$n \geq 3$$) and modifying it by taking two distinct vertices of the cycle and attaching (to each one) a new vertex. The resulting graph has no HP but is strongly connected and the removal of any vertex still leaves us with a strongly connected graph and thus has no "separation", leading to your algorithm falsely outputting that the original graph has a HP.