Collection of Maths Problems

Connected graph reduction

Task number: 4266

• Variant

  Every connected graph on \(n\ge 2\) vertices contains a vertex \(u\) such that the graph \(G\setminus\{u\}\) is connnected.

• Hint

  Consider the possible distances between vertices.

• Solution

  We choose vertex \(u\) so that it and some vertex \(w\) form the most distant pair in \(G\), i.e. their distance is maximal.

  If \(G\) was disconnected, then it would have two components, one containing \(w\) and the other containing at least one other vertex, denote some such \(z\).

  Every path from \(w\) to \(z\) passes through \(u\), so the length of the shortest path between \(w\) and \(z\) is sharply greater than the distance between \(u\) and \(w\), which contradicts the way they were chosen.

• Variant

  Every connected graph on \( n \ge 3 \) vertices contains two vertices \( u \) and \( v \) such that all three graphs \( G \setminus \{u \} \), \( G \setminus \{v \} \) and \( G \setminus \{u, v \} \) are connected.

• Hint

  Consider first cycles and paths.

• Solution

  First, select \(u\) by using the procedure described in the previous variant. Then choose a vertex \(v\) in the same way in the (connected) graph \(G\setminus\{u\}\). In the same way we argue that the graph \((G\setminus\{u\})\setminus\{v\}=G\setminus\{u,v\}\) is connected.

  It remains to show that the graph of \(G\setminus\{v\}\) is also connnected. At this point, we need to go back to the previous step and select the vertex \(v\) so that it is not adjacent to \(u\) if possible. Only when this is not possible, select \(v\) as an element of the most distant pair, even if it is adjacent to \(u\).

  We now consider two cases:

  • If \(u\) and \(v\) are not adjacent, then \(u\) in \(G\setminus\{v\}\) has a neighbor \(w\) that is connected to all other vertices in \(G\setminus\{u,v\}\). Therefore, in \(G\setminus\{v\}\), the vertex \(u\) is connected to all other vertices by a path through \(w\).
  • If \(u\) and \(v\) are adjacent, then \(u\) is also adjacent to vertex \(w\), which is the vertex farthest from \(v\) in the graph of \(G\setminus\{u\}\). As in the previous point, paths from \(u\) can then be directed through \(w\).

• Comment

  The sequential choice of vertices is based on the need to treat the following situations.

  If we take \(u\) and \(v\) to be the most distant pair of vertices in \(G\), then the proof would fail on, for example, the cycle \(C_4\).

  If we took \(v\) to be the most distant vertex pair in \(G\), and yet the second element of the pair was not adjacent to \(u\), then the argument would fail, for example, on the path \(P_3\).

• Variant

  Can the statement be extended for a triple of vertices \(u,v,w\) so that all 7 graphs obtained by removing any subset of this triple are connected?

• Solution

  No, e.g. if the graph is a path, then in each triple of vertices one separates the other two.