cutting vertex, graph theory I am having a trouble with an exercise (that, in fact, I saw one very similar here, if it's not the same, but I didn't understand the dialogue between the collaborators).
I have to demonstrate that any connected graph G with |V(G)|≥3 and at least 2 vertices that are not in a cycle must have a cut vertex.
My idea was to prove it by induction:  the base case is for 3 vertices, and the middle vertex will be the vertex cut. But what about N+1 vertices? How can you prove that xD? Is it a good idea to solve this problem by induction? Or exist another way?
 A: All non-complete graphs have a vertex cut: we delete all but two non-adjacent vertices to get a disconnected graph.  So I expect it should say "cut vertex" instead.
But then I think we only need 1 vertex v that's not in a cycle.

*

*If v has 2+ neighbors, then v is a cut vertex, otherwise there is a path between two distinct neighbors of v which does not include v, which implies that v was originally in a cycle (contradiction).


*If v has 1 neighbor, then its neighbor is a cut vertex: since there are 3+ vertices, deleting v's neighbor disconnects v from the remaining vertices.
(And v cannot have 0 neighbors, otherwise the graph is disconnected.)

If the question should say "has two distinct vertices u and v for which no cycle contains both u and v", then the above proof still works unless both u and v both belong to cycles.
We take a cycle containing u which minimizes the distance to v, and connect it to v with a shortest path.  Let x be the vertex where the cycle connects to the path.

Then x is a cut vertex, otherwise there is a path from the cycle to the x-v path that does not go through x, which can be used to construct another cycle containing u with less distance to v, giving a contradiction.

