Graph

A graph is a diagram consisting of a collection of vertices together with edges joining certain pairs of these vertices.

𝐺=[𝑣(𝐺),𝑒(𝐺)]

Graph Theory: - Graph Theory is the study of the relationship between vertices and edges.

Types of Graph: -

• Directed Graph: - In which the edges have a direction associated with them.

• Undirected graph: - In which all the edges are bidirectional.

• Null graph: - not any edges only vertices.

• Simple graph: - undirected and no loop and no multi edges.

• Multigraph: - multiple edges between the same set.

• Connected graph: - if any two vertices of the graph are connected by a path

• Disconnected graph: - a graph where any two vertices or nodes are disconnected by a path.

• Cycle graph: - if a graph consists of a single cycle, it is called a cycle graph.

• Complete graph: - when each pair of vertices are connected by an edge then such graph is called a complete graph.

• Planar graph: - when no two edges of a graph intersect and are all the vertices and edges are drawn in a single plane, then such a graph is called a planar graph

• Regular graph: - a graph is regular if all the vertices of the graph have the same degree.

• Bipartite graph: - if the vertex-set of graph G can be split into two disjoint sets, v1 and v2, in such a way that each edge in the graph joins a vertex in v1 to a vertex in v2, and there are no edges in G that connect two vertices in v1 or two vertices in v2, then the graph G, is called a bipartite graph.

• Homeomorphic graph: - The graphs G and G* are said to be homeomorphic if they can be obtained from the same graph or isomorphic graphs by this method, the graphs(a) and (b) are not isomorphic, but they are homeomorphic since they can be obtained from the graph(c) by adding appropriate vertices.

Representation of Graph: -

• Adjacency Matrix for undirected graph: - if an undirected group G consists of n vertices, then the adjacency matrix of a graph is an n*n matrix. 

𝐴=[𝑎𝑖𝑗]

• Adjacency matrix for directed graph: -

• Adjacent edge: - the non – parallel edges of the graph are called adjacent if they have one common vertex.
• Example: - the edge e1 = (a, b) and e4 = (a, c) are adjacent vertices as they have a common end vertex a.
• Open walk: - If a walk begins and ends with the different vertices, it is called an open walk.
• Closed walk: - If the initial and terminal vertices of a walk are the same, it is called a closed walk.
• Trivial walk: - A walk containing no edge and having length zero is called a trivial walk.
• Length of path: - The number of edges appearing in the sequence of the path is called the length of the path.

Circuit: - A circuit is a closed walk in which no vertex (except the initial and terminal vertex) appears more than once. In other words, a circuit is a closed, non-intersecting walk. A circuit is also called the cycle or elementary cycle or circular path or polygon.

Coloring: - suppose G be a simple graph with n vertices, we are to paint all its vertices such that no two adjacent vertices have the same color.

Chromatic Number: - The minimum number of colors needed to paint all the vertices of the graph such that no two adjacent vertices have the same color is called the chromatic number of G and denoted by C(G).

Example 1: The minimum number of colours that is sufficient to vertex-colour any planar graph is ______________.

Concept: - A planar graph is a graph in which no two edges cross each other. a vertex coloring of a graph is an assignment of colors to the vertices of graph such that adjacent vertices have different colors.

Explanayion: - According to the property of planar graph and four colour theorrems. Maximum number of colours that are needed to vertex-colour any planar graph is 4.

Example: - In this graph, only 3 colours are enough to colour this planar graph.

But if in this graph, there is an edge from a to d also, then three colours are not enough to vertex-colour this graph.

In this graph, 4 colours are needed to vertex-colour this graph.

Graph Isomorphism

• Graph Isomorphism is a phenomenon of existing the same graph in more than one form.
• Such graphs are called Isomorphic graphs.

• Graph Isomorphism Conditions
• Number of vertices in both the graphs must be the same.
• The number of edges in both graphs must be the same.
• The degree sequence of both the graphs must be the same.
• If a cycle of length k is formed by the vertices { v1, v2, ….., vk } in one graph, then a cycle of the same length k must be formed by the vertices { f(v1), f(v2), ….., f(vk) } in the other graph as well.
• Degree Sequence: - The degree sequence of a graph is defined as a sequence of the degree of all the vertices in ascending order.
• Example: -