×

## 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.

# Level 3

What is the least number of cuts that must be made in order to completely cut through this rope fence?

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.

Which of the shapes above cannot be traced without lifting up your pencil and without tracing over the same edge twice?

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?

The Queen plans to build a number of new cities in the wilderness, connected by a network of roads. She expects the annual tax revenues from each city to be numerically equal to the square of the population. Road maintenance will be expensive, though. The annual cost for each road is expected to be numerically equal to the product of the populations of the two cities that road connects. To keep the costs for road maintenance down, the Queen decrees that there should be only one way to get from any city to any other, and not more than three roads should connect to any given city (the attached design would be acceptable, for example). What is the largest number of cities the Queen can build without risking to lose money, regardless of the populations of the new cities and the design of the roads (subject to the two constraints mentioned above)?

Inspiration

A graph is a collection of vertices (points) joined by edges (line segments). A pair of vertices are adjacent if they are connected by an edge.

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.

×