29.1.1. Introduction to Tutorial 8

Try these first

1. 1.

   Define a Ramsey number.

   Hint

   Think about friendships among a group.

2. 2.

   What is an articulation point in a graph?

   Hint

   Imagine removing a friend from a friend circle.

3. 3.

   What is R(3, 3)?

   • Guarantees 3 friends
   • Guarantees 3 enemies
   • Both

   Hint

   Think about group dynamics!

4. 4.

   True or False: A tree with 5 nodes has 6 edges.

   • True
   • False

   Hint

   Remember the formula for trees.

5. 5.

   Create a graph with 10 nodes where every vertex is connected to exactly 4 others. Is it a tree, and if not, why?

   Hint

   Recall that trees must follow specific edge-node relationships.

6. 6.

   If a graph is self-complementary with 12 vertices, prove it must have 4k or 4k+1 vertices.

   Hint

   Think about how edges are distributed between complementary graphs.