Let G be an arbitrary graph with at least 2 vertices. We construct a graph H by adding two vertices x and y to G, with every possible edge between vertices of G and x, y. Prove that H will never have any cut vertices, no matter what graph G we start with.
This article should give you a good starting point.
www.tutorialspoint.com/graph_theory/graph_theory_connectivity.htm
To prove that the graph H will never have any cut vertices, we need to show that there is always a path between any two vertices in H. In other words, for any two vertices u and v in H, there exists a sequence of vertices such that we can travel from u to v.
Let's consider the construction of graph H. We add two vertices, x and y, to the graph G and connect them to every vertex of G. Now, let's choose any two vertices, u and v, in H.
Case 1: If both u and v are in G (i.e., not the newly added vertices x and y), then there already exists a path between u and v in G by definition.
Case 2: If either u or v is either x or y, without loss of generality, let's assume u = x. Since x is connected to every vertex of G, there exists a path between x and any vertex in G. Similarly, there also exists a path between v and any vertex in G. Thus, we can combine these two paths to form a path from u to v in H.
Case 3: If one vertex is in G and the other is either x or y, suppose without loss of generality that u is in G and v is y. Since y is connected to every vertex of G, there exists a path between y and any vertex in G. Furthermore, since u is a vertex in G, there is a path between u and v in G. Thus, we can combine these two paths to form a path from u to v in H.
Therefore, in all cases, there exists a path between any two vertices in H. This means that H does not have any cut vertices, as removing any vertex would not disconnect the graph.
In conclusion, the construction of graph H ensures that there are always paths between any two vertices, eliminating the possibility of cut vertices.