A new airline "Capitals Direct" has direct flights operating on the following routes (in both directions): Paris - London, Paris - Lisbon, Rome - London, Rome - Madrid, Berlin - Helsinki, Berlin - Amsterdam, Amsterdam - Prague. These are the only flights that the company offers. I would like to travel from Paris to Amsterdam. I cannot buy a direct ticket for sure, but can "Capitals Direct" offer me a connecting flight?
Can one arrange numbers from \(1\) to \(9\) in a row so that each pair of consecutive numbers forms a two-digit multiple of \(7\) or a multiple of \(13\)?
In the Royal Grammar School all Year \(9\) students were gathered in the Queen’s Hall for an important announcement. They have been waiting for it for a while and everyone had enough time to greet every other student with a handshake. Assuming there are \(100\) Year \(9\) students at the school, how many handshakes were made before the announcement?
In \(2149\) a regular transport connection between nine planets of the Solar System was introduced. Space capsules are flying between the following pairs of planets: Earth – Mercury, Pluto – Venus, Earth – Pluto, Pluto – Mercury, Mercury – Venus, Uranus – Neptune, Neptune – Saturn, Saturn – Jupiter, Jupiter – Mars, and Mars – Uranus. Is it possible to travel from Earth to Mars by using this type of transport with possible changes at other planets?
Is it possible to find a way of arranging numbers from \(0\) to \(9\) in a row so that each pair of consecutive numbers adds up to a multiple of \(5\), \(7\), or \(13\)?
Airlines connect pairs of cities. How can you connect 50 cities with the fewest number of airlines so that from every city you can get to any other city by taking at most two flights?
In the town of Ely, all the families have separate houses. On one fine day, each family moved into another, one of the houses house that used to be occupied by other families. They afterwards decided to paint all houses in red, blue or green colors in such a way that for each family the colour of the new and old houses would not match. Is this always possible to paint te houses in such a way, regardless of how families decided to move?
Let’s prove the following statement: every graph without isolated vertices is connected.
Proof We use the induction on the number of vertices. Clearly the statement is true for graphs with \(2\) vertices. Now, assume we have proven the statement for graphs with up to \(n\) vertices.
Take a graph with \(n\) vertices by induction hypothesis it must be connected. Let’s add a non-isolated vertex to it. As this vertex is not isolated, it is connected to one of the other \(n\) vertices. But then the whole graph of \(n+1\) vertices is connected!
A graph is called Bipartite if it is possible to split all its vertices into two groups in such a way that there are no edges connecting vertices from the same group. Find out whic of the following graphs are bipartite and which are not: