29.2.3. Articulation Points

Try these first

1. 1.

   What is an articulation point?

   Hint

   Think about what would happen to a graph if you remove a point.

2. 2.

   Is a single node in a graph always an articulation point?

   Hint

   Consider a graph with just one vertex.

3. 3.

   What is true about articulation points?

   • They always exist in any graph
   • They disconnect the graph when removed
   • They can exist in disconnected graphs

   Hint

   Think about the definition of articulation points.

4. 4.

   True or False: A graph can be fully disconnected while still having every vertex as an articulation point.

   • True
   • False

   Hint

   Remember what it means for a vertex to be an articulation point.

5. 5.

   Consider a graph with 7 nodes where each node connects to exactly 4 others in a non-circular fashion. Investigate whether any nodes can be articulation points and justify why.

   Hint

   Think about pairs of nodes and consider their connectivity.

6. 6.

   Create a situation in a friendship network with 10 people where any group of three will always consist of either all friends or all enemies, thus demonstrating the Ramsey number relevance in social networks.

   Hint

   Visual dynamics of connecting different groups will help reveal this.