Graph only consisting of separating vertices

Question

In a finite graph $G=(V,E)$ a vertex $v \in V$ is a separating vertex if $G(V\backslash \{v\})$ (the graph without $v$) has more connected components than $G$. Prove or disprove: there exists a graph which only consists of separating vertices.

I'm just solving this exercise. It is quite obvious that there can't be such a graph but so far I haven't found a way to prove it in a mathematically pleasing way.

My first plan was to use the fact that in a graph with only separating vertices, every vertex has degree greater than $2$ and then show that it's 2-connected.

Answer 1

Without loss of generality assume $G$ is connected. Suppose $G$ has only separating vertices.

Let $v$ be the vertex such that the smallest component of $G \setminus \{v\}$ is as small as possible. This smallest component cannot have size $1$ or $2$, else one of the vertices in this component would not be a separating vertex of $G$.

Consider a vertex $v'$ in this smallest component $C$. Recall it is a separating vertex of $G$.

• If it were a separating vertex of $C$, then one of the components of $G \setminus \{v'\}$ would be smaller than $C$, which contradicts minimality of $C$.
• Thus $v'$ is not a separating vertex of $C$, which then implies it must be the only vertex of $C$ adjacent to $v$. But this also leads to a contradiction, since $C \setminus \{v'\}$ would be a component of $G \setminus \{v'\}$ that is smaller than $C$.

Answer 2

$V= \{ i \mid i \in \mathbb{Z} \}$ and $E= \{ (i,i+1) \mid i \in \mathbb{Z} \}$.

Answer 3

Let $H$ be a connected component of $G,$ let $T$ be a spanning tree of $H,$ and let $v$ be a leaf vertex of $T;$ then $v$ is not a separating vertex of $G.$

Answer 4

If G is a finite graph then:

1- $G$ is acyclic, in which case it most have a vertex of degree 1 that is not a separating vertex

2- $G$ is cyclic, therefore, any vertex in a cycle is not a separating vertex, because between any two vertices have a path between them (if the path between them that existed in $G$ went thru the vertex you erased then you just go thru the rest of the cycle).