In a connected graph which is not complete, can we find three vertices denoted by a,b,c such that a is adjacent to b, b is adjacent to c, but a and c are not neighbors?
That's a graph theory problem in my CS textbook called Graph Theory & Algorithm. After learning the definition of the cut vertex and the bridge and the Tarjan algorithm for finding the cut vertex, my teacher raised this problem. It is obvious to some extent but the formalized verification is necessary.
I tried to assume to the converse that we can't find such three vertices. And then there are three situations to consider: there are no or one or three pairs of neighbors among the arbitrary three vertexes of this graph. That confused me a lot.
Since the graph is incomplete, there are two vertices, say A and Z, with no edge AZ in the graph. Since the graph is connected, there is some path A B C … X Y Z. There is at least one vertex on this path with an edge to Z, since Y is one. Let Q be the first such vertex. Let P be the preceding vertex on the path. Then PZ is not in the graph but PQ and QZ are.