There are $n$ cities in a country. Between any two cities there is at most one road. Suppose that the total number of roads is $n.$ Prove that there is a city such that starting from there it is possible to come back to it without ever travelling the same road twice.
Problem
Source:
Tags: combinatorics
laegolas
10.02.2017 06:32
It is well known that given a graph with $n$ vertices and $n$ edges there must exist at least one cycle.
Olympus_mountaineer
05.03.2019 20:36
Ramanujan_1729 wrote: There are $n$ cities in a country. Between any two cities there is at most one road. Suppose that the total number of roads is $n.$ Prove that there is a city such that starting from there it is possible to come back to it without ever travelling the same road twice. This is Bangladesh National Mathematical Olympiad 2013 Higher Secondary P6
snayer945gmail.com
19.03.2020 20:49
consider the cities as nodes and roads between them as edges. ATQ,there are n nodes and n edges. SINCE, no of edges = nodes. therefore the graph must contain at least one cycle. WE ARE DONE !