Problem #DES-graphs

Descriptions

Problem

Sometimes it is hard to rigorously formulate an intuitively correct reasoning. We might not know the proper words, the proper language, we might not have the right tools. Maths problems are not an exception. When we start learning to solve them, we know nothing about possible mathematical approaches and mathematical models. Today you will learn a very useful way to visualise information: you will learn how to represent information as a graph.

A graph is a finite set of points, some of which are connected with line segments. The points of a graph are called vertices. The line segments are called edges. In this problem set we only consider graphs in which every pair of vertices is connected with one or zero edges.

In a mathematical problem, one may use vertices of a graph to represent objects in the problem, i.e. people, cities, airports, etc, and edges of the graph represent relations between the objects such as mutual friendship, railways between cities, plane routes, etc. As you will see in the examples below, representing the initial problem as a graph can considerably simplify the solution.