An Introduction on Graph Theory �
Dr. Kalyani Maity Das
Department of Mathematics
Belda College
Definition: �A graph G=(V,E) consists of a set of objects V={v1, v2,…} called vertices and another set E={e1, e2,…}, whose elements are called edges, such that each edge ek is identified with an unordered pair (vi, vj) of vertices. The vertices vi, vj associated with edge ek are called the end vertices of ek. Fig.1 is the diagram of a graph.
����� � Fig.1: Graph with five vertices and seven edges��An edge associated with vertex pair (vi,vj). An edge having the same vertex as both its end vertices is called a self loop. The edge e1 of Fig.1 is self loop. The edges e4 and e5 are parallel edges. That is, more than one edges associated with a given pair of vertices called parallel edges.
e1
e2
e3
e4
e5
e6
e7
v1
v2
v3
v4
v5
It should be noted that the important thing to draw a graph is the incidence between the edges and vertices whether the lines are drawn straight or curve, long or short. In Fig.2 (a) and (b) are same, because incidence between edges and vertices is the same in both cases.����� � Fig. 2: Same graph drawn differently
1
2
3
4
1
2
4
3
(a)
(b)
Incidennce and degree:�When a vertex vi is an end vertex of some edge ej, vi and ej are said to be incident with each other.� For example, in Fig. 1, edges e2, e6 and e7 are incident with vertex v4.� The number of edges incident on a vertex vi, with self-loops counted twice, is called the degree, d(vi), of vertex vi. � For example, in Fig. 1, d(v1)=d(v3)=d(v4)=3. The degree of a vertex is sometimes also referred to as its valency. � The most important result is that the sum of the degrees of all vertices in G is twice the number of edges in G. That is,�
Isolated Vertex:�A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are vertices with zero degree. The vertices v4 and v7 in Fig. 3 are the isolated vertices.������ Fig. 3: Graph containing isolated vertices, � series edges and a pendent vertex
v2
v3
v4
v7
v1
v6
v5
Pendent Vertex:�A vertex of degree one is called a pendent vertex or end vertex. � Vertex v3 in Fig. 3 is a pendent vertex.���Series Edges:�Two adjacent edges are said to be in series if their common vertex is of degree two.� In Fig. 3, two edges incident on v1 are in series.
There are various types of graphs are in literature. Some of them are simple graph, finite and infinite graph, null graph, planar graph, Euler graph, connected and disconnected graph, complete graph, tree, cactus graph, etc.��Simple graph:�A graph that has neither self-loops nor parallel edges is called a simple graph. In some graph-theory literature, a graph is defined to be only a simple graph but in most engineering applications it is necessary that parallel edges and self-loops be allowed.
Finite and infinite graph:�A graph with a finite number of vertices as well as finite number of edges is called a finite graph; otherwise, it is an infinite graph.� The graphs in Fig.1, 2 and 3 are all examples of finite graphs. Portion of a infinite graph is shown in Fig.4.������ Fig. 4: Portion of a infinite graph
Null graph:�In a graph G=(V,E), it is possible for the edge set E to be empty. Such a graph without any edges, is called a null graph. That is, every vertex of the null graph is an isolated vertex.������� Fig. 5: Null graph with six vertices
Subgraphs:�A graph g is said to be a subgraph of a graph G if all the vertices and all the edges of g are in G and each edge of g has the same end vertices in g as in G.� The graph in Fig. 6(b) is a subgraph of the one in Fig. 6(a).������ Fig. 6: Graph (a) and one of its subgraph (b)
Walk:�A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident with the vertices preceding and following it. No edge appear more than once in a walk but a vertex may appear.� In Fig. 7, v1av2bv3cv3dv4ev2fv5 is a walk. It is an open walk as the beginning and ending vertices are different.������� Fig. 7: A graph
c
g
a
f
h
b
e
d
v1
v2
v3
v4
v5
Path:�An open walk in which no vertex appear more than once is called a path. � In Fig. 7, v1av2bv3dv4 is a path.��Circuit:�A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a circuit. That is, circuit is a closed, non-intersecting walk. � In Fig. 7, v2b v3dv4ev2 is a circuit.
Connected and disconnected graph:�A graph G is said to be connected if there is at least one path between every pair of vertices in G, otherwise, G is disconnected.� A disconnected graph consists of two or more connected graphs. Each of this connected graphs is called component.������� Fig. 8: A disconnected graph with two component
Euler graph:�If some closed walk in a graph contains all the edges of the graph, then the walk is called an Euler line and the graph an Euler graph. Euler graph is always connected.������� Fig. 9: Examples of two Euler graphs
Complete graph:�A simple graph in which there exists an edge between every pair of vertices is called a complete graph. A complete graph is sometimes referred to as a universal graph or clique.� Degree of every vertex is n-1 in a complete graph G of n vertices and total number of edges is n(n-1)/2.� Complete graph of two, three, four and five vertices are shown in Fig. 10.������Fig. 10: Complete graph of two, three, four and five vertices
Planar graph:�A planar graph is a graph that can be drawn in the plane in such a way that no two edges cross. That is, no two edges intersect geometrically except at a vertex to which both are incident. Any such drawing is a plane drawing (graph). A drawing of geometric representation of a graph on any surface without a crossover between its edges is called an embedding of a graph. A graph which is not planar is called non-planar graph.� A graph with crossing edges does not implies that it is non-planar. There may be alternating way to draw the graph without crossing the edges. �
���� � Fig. 11: (b) and (c) are planar graphs��For example, in Fig. 11, three drawing of the same graph K4 are given, but only the graphs of Fig. 11(b) and (c) are planar graphs.� From this figure leads one important question. Whether planar graph can be draw in the plane so that each edge represented by a straight line? Self-loops and parallel edges canot be drawn as straight lines, but every simple planar graphs can drawn with straight lines.
Bipartite graph:�A graph G is said to be bipartite if and only if it is possible to partition V(G) into two subsets Sj, j=1,2, such that every edge of E(G) joins a vertex of Si to a vertex Sj where The graph G of Fig. 12 is a bipartite graph. Again S1={u1, u2, u3, u4} and S2={v1, v2, v3, v4}.������ Fig. 12: A bipartite graph
u1
u2
u3
u4
v1
v2
v3
v4
Tree: Definition�A connected cycle free graph is called tree.��������� Trees with one, two, three and four vertices�
a
b
c
d
(i)
(ii)
(iii)
(iv)
Applications of trees:
etc.
Some properties of trees:
etc
A theorem:
For a graph G with n vertices, the following are equivalent:
Representation of Paraffins (CnH2n+2)
First three paraffins
Two different representations of C4H10� (Isobutane)�
�Cactus Graph: Definition�Cactus graph is a connected graph in which every block is a cycle or an edge, in other words, no edge belongs to more than one cycle. ��
An example of Cactus Graph
Applications of cactus graphs
etc
References: