× back Konigsberg bridge problem Graph definition Finite and Infinite graph Adjacent node (vertices) Isolated nodes Incident Simple graph Loop Parallel edges Multigraph Pseudo graph Directed and Undirected graph Degree of vertex In degree and out degree
Next Topic → ← Previous Topic

Graph theory

Konigsberg Seven Bridge Problem:

Graph

Finite graph and Infinite graph

Adjacent node (vertices)

Isolated nodes

Incident

Simple graph

Loop

Parallel edges

Multigraph

Pseudo graph

Directed graph and Undirected graph

Undirected graph

Degree of vertex

In degree and out degree

Types of graph

Null Graph

  • A graph which contains only isolated vertices is called a null graph.
  • The set of edges in a null graph is empty.
  • Null graph on 'n' vertices denoted by Nn.

Connected graph

  • If there exist at least one path between any two vertices of a graph G(V, E), then it is called a connected graph.
  • If graph is not connect then it is called a disconnected graph.

Complete graph

  • A graph G(V, E) is said to be complete graph if every vertex in G is connected to all other vertices of G.
  • A complete graph is usually denoted by Kn.

Regular graph

  • A graph in which all vertices are of equal degree is called a regular graph.
  • If the degree of each vertex is 'r' then the graph is called a regular graph of degree 'r'.

Cycle graph

  • A connected graph whose edges form a cycle of length 'n' is called a cycle graph of order n.
  • Cycle graphs of length 'n' is denoted by Cn.
  • For a cycle graph n >= 3;

Wheel graph

  • The wheel graph is denoted by Wn (n > 3) is obtained from Cn by adding a vertex 'v' inside Cn and connecting it to every vertex in Cn.

Wn is a regular graph for n = 3. It has n + 1 vertices & 2n edges.

Path graph

  • If we remove an edge from a Cn graph then such graph is called a path graph of order 'n'. It is denoted by Pn.

Adjacency Matrix

Representation of undirected graph using adjacency matrix

  • Since adjacency matrix representation is based on ordering of vertices in a graph, therefore, for a graph with n vertices, we may construct as many as n! different adjacency matrices.

Some important result about the adjacency matrix

  1. The adjacency matrix A is symmetric i.e., aij = aji ∀ i & j.
  2. The number of non-zero elements in the matric is equal to the sum of degree of all vertices of the graph.
  3. The adjacency matrix has n2 elements.
  4. The entries along the principal diagonal of A are all 0's if and only if the graph has no self loops.

Adjacency matrix (for a directed graph)

Use adjacency matrix to represent the graph.

Incidence Matrix

Representation of undirected graph

Representation of directed graph

Spanning subgrap

Isomorphic Graphs

Bi-partite graph

Handshaking theorem

Proof → Consider a graph G(V, E) with m edges and n vertices i.e.,
V = {v1, v2, v3, ..., vn}
E = {e1, e2, e3, ..., em}
Since degree of vertex is defined as the number of edge connected with it. And every edge is connected with exactly two vertices so each edge is counted twice at each of its end. This implies that the sum of the degrees of all vertices in G is twice the number of edges in G.

Theorem → The number of vertices of odd degree in a graph G is always even.

Sub graphs

Note ↓

  1. A graph G is a subgraph of itself. A null graph is also a subgraph of G.
  2. A subgraph of a subgraph of G is a subgraph of G.
  3. A single vertex in a graph G is a subgraph of G.

Q- Find the different subgraphs of this graph.


Operations of graphs

Union of graphs

  • Let G1(V, E) and G2(V, E) are two graphs then their union will be a graph such that
    V(G1 ⋃ G2) = V(G1) ⋃ V(G2)
    E(G1 ⋃ G2) = E(G1) ⋃ E(G2)

Intersection of graph

  • Let G1(V, E) & G2(V, E) are two graphs with at least one vertex in common then their intersection will be a graph such that
    V(G1 ⋂ G2) = V(G1) ⋂ V(G2)
    E(G1 ⋂ G2) = E(G1) ⋂ E(G2)

Sum of two graphs

  • Let G1(V,E) & G2(V, E) are two graphs such that V(G1) ⋂ V(G2) = ∅
    then the sum G1 + G2 is defined as the graph whose vertex set is V(G1) + V(G2) and the edge set is consisting those edges, which are in G1 and in G2 and the edges obtained, by joining each vertex of G1 to each vertex G2.

Ring sum of graphs

  • Let G1(V, E) and G2(V, E) be two graphs then the ring sum of G1 and G2 denoted by G1 ⨁ G2, is defined as the graph G such that
    (i) V(G) = V(G1) ⋂ V(G2)
    (ii) E(G) = E(G1) U E(G2) - E(G1) ⋂ E(G2)

Complement of a graph

  • The complement G' of simple graph G(V, E) is the simple graph with vertex set V(G) such that edge vi vj ∈ E(G) iff vi vj ∉ E(G')

Lectures ↓