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
edge joining some pair of vertices then these edges are called multiple edges.
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 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.
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.
A circuit is path that begins and ends at the same vertex.
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.
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.
An Euler path is a path that travels through all edges of a connected graph.
An Euler circuit is a circuit that visits all edges of a connected graph.
The Hand Shaking Lemma
The sum of the degrees of all the vertices of a graph is twice the number
of edges in the graph.