3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ That's a good approach, and proves that any finite graph has a vertex which is not separating. $\endgroup$ – Mike Earnest May 13 '18 at 21:17
  • $\begingroup$ But how do I get there? Is there a special characteristic that a seperating vertex has regarding its edges that I can use? $\endgroup$ – d237 May 13 '18 at 21:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Mike Earnest May 13 '18 at 21:37
  • $\begingroup$ 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? $\endgroup$ – d237 May 13 '18 at 21:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Mike Earnest May 13 '18 at 22:01
5
$\begingroup$

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$.
$\endgroup$
6
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – d237 May 13 '18 at 21:18
  • 4
    $\begingroup$ @d237 This is an infinite "line" graph, so there is no "first" or "last" vertex. $\endgroup$ – angryavian May 13 '18 at 21:20
  • 1
    $\begingroup$ Oh, sorry. I should have made clear that I talk about finite graphs in my exercise. $\endgroup$ – d237 May 13 '18 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.