# Graph only consisting of separating vertices

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.

• That's a good approach, and proves that any finite graph has a vertex which is not separating. – Mike Earnest May 13 '18 at 21:17
• But how do I get there? Is there a special characteristic that a seperating vertex has regarding its edges that I can use? – d237 May 13 '18 at 21:30
• Just prove that a separating vertex cannot have $0$ or $1$ edges. This is because if a vertex $v$ has degree $\le 1$, then it cannot be a part of any path, as the middle vertices in a path have $\ge2$ neighbors, so deleting $v$ does not break any paths. – Mike Earnest May 13 '18 at 21:37
• Sorry my writing is a bit confusing. That's the step I already understood, my problem is what to do after that. Just because every vertex has degree greater than two doesn't make a vertex appear which isn't seperating, or does it? – d237 May 13 '18 at 21:55
• OK, I was wrong, every vertex having degree $\ge 2$ does not imply the graph is $2$-connected. But I am writing up an answer now. – Mike Earnest May 13 '18 at 22:01

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

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

• +1 This is much nicer than my own answer. – angryavian May 14 '18 at 15:54

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

• Ok, to be honest I'm not so sure what you mean by that. This is a graph where every vertex is connected with exactly one edge with both his neighbours. But the first and the last vertex aren't seperating vertices? – d237 May 13 '18 at 21:18
• @d237 This is an infinite "line" graph, so there is no "first" or "last" vertex. – angryavian May 13 '18 at 21:20
• Oh, sorry. I should have made clear that I talk about finite graphs in my exercise. – d237 May 13 '18 at 21:21