GRAPH THEORY
A graph G = (V, E) consists of a set V of vertices (also called nodes) and a set E of edges
A graph G consists of a set V(G) of elements called vertices and a set E(G) of elements called
edges together with a relation of incidence which associates each edges with a pair of
vertices, called its ends.
Parallel Edges: Two or more edges joining the same pair of vertices are known as a multiple
edge, If two or more edges have the same endpoints then they are called multiple or parallel
edges. In the figure e4 and e5 are parallel edges.
Loop: An edge joining a vertex to itself is called a loop. . If an edge has only one endpoint
then it is called a loop edge
The following figure is shown as a loop and multiple edges of a graph. Where, V = V(G)=the
number of vertices={v1, v2, v3, v4} E = E(G)=the number of edges={e1, e2, e3, e4, e5} In
the figure an edge e6 is a loop, and two edges e4 and e5 are multiple edges.
Simple graph: Simple graph and trivial graph A
graph with one vertex is called trivial and all
other graphs are nontrivial. A graph with no
loops and multiple edges is called a simple graph
shows in the following figure.
Adjacent Vertices: Two vertices that are joined by an edge are called adjacent vertices.
In the figure v1 and v2 are adjacent vertices. V1 and v4 are adjacent vertices.
Degree of Vertex: It is the number of vertices adjacent to a vertex V.It is denoted by deg(V).
deg(a) = 2, deg(b) = 3, deg(c)= 1, deg(d) = 2, deg(e) = 0
Isolated vertex: Vertex which is not connected to other. Degree of isolated vertex is zero. In
the figure vertex ‘e’ is isolated vertex.
A graph G = (V, E) consists of a set V of vertices (also called nodes) and a set E of edges
A graph G consists of a set V(G) of elements called vertices and a set E(G) of elements called
edges together with a relation of incidence which associates each edges with a pair of
vertices, called its ends.
Parallel Edges: Two or more edges joining the same pair of vertices are known as a multiple
edge, If two or more edges have the same endpoints then they are called multiple or parallel
edges. In the figure e4 and e5 are parallel edges.
Loop: An edge joining a vertex to itself is called a loop. . If an edge has only one endpoint
then it is called a loop edge
The following figure is shown as a loop and multiple edges of a graph. Where, V = V(G)=the
number of vertices={v1, v2, v3, v4} E = E(G)=the number of edges={e1, e2, e3, e4, e5} In
the figure an edge e6 is a loop, and two edges e4 and e5 are multiple edges.
Simple graph: Simple graph and trivial graph A
graph with one vertex is called trivial and all
other graphs are nontrivial. A graph with no
loops and multiple edges is called a simple graph
shows in the following figure.
Adjacent Vertices: Two vertices that are joined by an edge are called adjacent vertices.
In the figure v1 and v2 are adjacent vertices. V1 and v4 are adjacent vertices.
Degree of Vertex: It is the number of vertices adjacent to a vertex V.It is denoted by deg(V).
deg(a) = 2, deg(b) = 3, deg(c)= 1, deg(d) = 2, deg(e) = 0
Isolated vertex: Vertex which is not connected to other. Degree of isolated vertex is zero. In
the figure vertex ‘e’ is isolated vertex.
