Back to all chapters
# Graph Theory

Any connected group of things can be represented as a graph: cities and roads, people and friendships, and more. Learn why an even number of people have an odd number of friends.

Note: The knots where multiple ropes meet are too thick to cut through. There is a beautiful way to solve this that is much more elegant than randomly attacking the fence with scissors.

Alice invited seven of her friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once.

After the party, Alice asked each of her seven friends how many people they shook hands with during the party, and was surprised when they responded with seven distinct positive integers.

Given that her friends were truthful, how many hands did Alice shake?

Coloring a graph refers to assigning colors to its vertices. A graph is said to be **properly colored** if every pair of adjacent vertices receive different colors.

Consider the above graph with 4 vertices and 4 edges. This graph is denoted as \(C_{4} \). If you are permitted to use 6 different colors, how many proper coloring does \(C_{4} \) have ?

**Note:**

1. Vertices are adjacent if they are joined by an edge (line).

2.The coloring that is in the figure is an example of proper coloring.

×

Problem Loading...

Note Loading...

Set Loading...