Graph Theory
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.
by
Zandra Vinegar
Which of the shapes above cannot be traced without lifting up your pencil and without tracing over the same edge twice?
by
Andrew Ellinor
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?
by
Maggie Miller
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).
Unfortunately, Parliament is responsible for deciding which roads will be built (subject to the two Queen's decrees) and how many people live in each city, but has no concern for attempting to stay financially solvent (meaning tax revenue \( \geq \) road maintenance). Regardless of what Parliament decides, what is the largest number of cities that the Queen can build without risking to lose money?
by
Otto Bretscher
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.
by
Pramath Anamby