Graph is all about dots and lines connecting them. Or we can simply say that a Graph is a collection of * vertices* (also called

*) and*

**nodes***(*

**edges***). So when talking about*

**connections**between nodes*, it is just points and lines connecting them. Now, let’s begin with more formal discussion on Graph Theory.*

**Graph Theory**## Graph Theory | Basic Terminology

* definition of Graph:* A graph

*is a non empty finite set of vertices*

**G***along with a set of edges*

**V***(*

**E***also*) of unordered pair of distinct vertices, or subsets of

**incidents**between vertices*. So we can say a*

**V***,*

**Graph***= <*

**G***,*

**V***>.*

**E*** Terminology:* Here, we can see in above figure that points indicate

*(*

**vertices***,*

**a***, ..), and lines that join vertices are*

**b***. From the*

**edges***we have learned that edges are unordered pairs of vertices. Therefore it is common to denote an edge consisting vertices. Such as, we can denote edge $E_{1}$ consisting vertices*

**definition***,*

**a***. So, $E_{1}$= {*

**b***,*

**a***}, which is a subset of vertices*

**b***= {*

**V***,*

**a***,*

**b***,*

**c***,*

**d***,*

**e***}. In graph theory, the notion of {*

**f***,*

**b***} denotes the same*

**a****as {**

*edge**,*

**a***} for*

**b****. Any edge $E_{1}$= {**

*undirected graph**,*

**a***} in graph theory, the vertices*

**b***, and*

**a***are the ends of the edge $E_{1}$. Therefore,*

**b*** Incident:* $E_{1}$ is an incident to both

*, and*

**a***.*

**b**

**Adjacent:***is adjacent to vertices*

**a***,*

**b***, and*

**e***.*

**f***adjacent to*

**e***. We often call adjacent vertices neighbour.*

**a***For any vertex*

**Degree of Vertex:***, the degree of*

**a***denoted deg(*

**a***a*), is the number of

*incident to it.*

**edges***A vertex is even, or odd if its degree is even or odd.*

**Even or Odd:***A vertex of degree zero, means no edges or incident refers to as isolated vertex.*

**Isolated vertex:**### Types of Graph

There are two types of graph: * Undirected*, and

*. In undirected graph edge $E_{1}$= {*

**Directed***,*

**a***}, same as writing {b, a}. Because in undirected graph we do not consider direction, so order does not matter. But in directed graph order does matter. Therefore we label this as ordered pair. So, $E’_{1}$= <a, b>, that means we say, we have a*

**b***coming from*

**tail***and we have a*

**a***going to*

**head***. So, $E’_{1}$= (a → b).*

**b**## Graph Traversing or walk Through the Graph | x-y walk

A walk in a graph is a sequence of vertices and edges. So,

Walk * W* =

*$e_{1}v_{1}e_{2}v_{2}e_{3} … v_{n-1}e_{n}$*

**x***. Here, we start from*

**y***then we take some edge $e_{1}$, then get another vertex $v_{1}$ so on and so forth until we get to*

**x***.*

**y**Now from above Graph * G* the set of vertices

*= {a, b, c, d, e, f, g}. The set of edges*

**V***= {{a, b}, {a, c}, {a, d}, {b,e}, {b, c}, {e, f}}.*

**E*** Cardinality of Graph:* Cardinality of Graph represents the number of vertices. Absolute value of G |

*| denotes the cardinality of the Graph. So, |*

**G***| =*

**G****7**. Degree of vertex a, deg (

*) = 3. Because the number of*

**a***coming out from*

**edges***is 3.*

**a***:*

**Adjacency list of the graph**a: b, c, d

b: a, c, e

c: a, b

d: a

e: b, f

f: e

g: isolated vertex

** Adjacency Matrix:** in graph theory,

*adjacency matrix*is a matrix configuration that shows the connection of vertices between one another. This is the matrix form of above

*adjacency list of graph*. Vertex that connected with other vertices we represent them in the matrix with

**. -and the vertex that has no edges between other vertices, we represent them with**

*1***.**

*0*

There is also an idea of graph ** isomorphism**, which is a graph of same number of vertices and same number of edges but connected different way.

**read here>>**//This is the end of general discussion on graph theory. Read more articles on ** Discrete Mathematics**,

**here>>**