Graph Theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Any diagram of points and line segments connecting pairs of points is called a graph. The points are usually called vertices or nodes, and the line segments are called edges. More than one edge is allowed to connect the same pair of vertices to yield a set of multiple edges. One can also permit an edge connecting a vertex to itself via a loop. Edges can intersect, but the places where they cross are not considered vertices.

A graph that comes in just one piece is called connected. This means that it is always possible to travel from any one vertex to any other by traversing a sequence of edges.

The degree (or valence) of a vertex is the number of edges that meet at that vertex. Loops are counted twice. A graph is called complete if every vertex is connected to each and every other vertex by a single edge. For example, the complete graph on four vertices looks like a square with the two