Problems

a) In Wonderland, there are three cities \(A\), \(B\) and \(C\). 6 roads lead from city \(A\) to city \(B\), and 4 roads lead from city \(B\) to city \(C\). How many ways can you travel from \(A\) to \(C\)?

b) In Wonderland, another city \(D\) was built as well as several new roads – two from \(A\) to \(D\) and two from \(D\) to \(C\). In how many ways can you now get from city \(A\) to city \(C\)?

Prove that a graph, in which every two vertices are connected by exactly one simple path, is a tree.

Prove that, in a tree, every two vertices are connected by exactly one simple path.

Eugenie, arriving from Big-island, said that there are several lakes connected by rivers. Three rivers flow from each lake, and four rivers flow into each lake. Prove that she is wrong.

Several Top Secret Objects are connected by an underground railway in such a way that each Object is directly connected to no more than three others and from each Object one can reach any other Object by going and by changing no more than once. What is the maximum number of Top Secret Objects?

We wish to paint the \(15\) segments in the picture below in three colours. We want it such that no two segments of the same colour have a common end. For example, you cannot have both \(AB\) and \(BC\) blue since they share the end \(B\). Is such a painting possible?

There is a scout group where some of the members know each other. Amongst any four members there is at least one of them who knows the other three. Prove that there is at least one member who knows the entirety of the scout group.

In a distant village, there are \(3\) houses and \(3\) wells. Inhabitants of each house want to have access to all \(3\) wells. Is it possible to build non-intersecting straight paths from each house to each well? All houses and well must be level (that is, none of them are higher up, like on a mountain, nor are any of them on lower ground, like in a valley).