# Basic Graph Theory

• Graph
A graph is a mathematical structure consisting of a set of points called VERTICES and a set (possibly empty) of lines linking some pair of vertices. It is possible for the edges to oriented; i.e. to be directed edges. The lines are called EDGES if they are undirected, and or ARCS if they are directed.

• Loop and Multiple edges
A loop is an edge that connects a vertex to itself. If a graph has more than one edge joining some pair of vertices then these edges are called multiple edges.

• Simple Graph
A simple graph is a graph that does not have more than one edge between any two vertices and no edge starts and ends at the same vertex. In other words a simple graph is a graph without loops and multiple edges.

Two vertices are said to be adjacent if there is an edge (arc) connecting them.

Adjacent edges are edges that share a common vertex.

• Degree of a Vertex
The degree of a vertex is the number of edges incident with that vertex.

• Path
A path is a sequence of vertices with the property that each vertex in the sequence is adjacent to the vertex next to it. A path that does not repeat vertices is called a simple path.

• Circuit
A circuit is path that begins and ends at the same vertex.

• Cycle
A circuit that doesn't repeat vertices is called a cycle.

• A Connected Graph
A graph is said to be connected if any two of its vertices are joined by a path. A graph that is not connected is a disconnected graph. A disconnected graph is made up of connected subgraphs that are called components.

• Bridge
A bridge is an edge whose deletion from a graph increases the number of components in the graph. If a graph was a connected graph then the removal of a bridge-edge disconnects it.

• Euler Path
An Euler path is a path that travels through all edges of a connected graph.

• Euler Circuit
An Euler circuit is a circuit that visits all edges of a connected graph.

## The Hand Shaking Lemma

1. The sum of the degrees of all the vertices of a graph is twice the number of edges in the graph.
2. The number of vertices of odd degree is always even.
An applet on the Hand shaking Lemma