hamburger

Graph Theory Discrete Mathematics Study Notes (Part-1)

By BYJU'S Exam Prep

Updated on: September 25th, 2023

Graph Theory Discrete Mathematics Study Notes (Part-1)- Graph: A graph G is defined by G = (V, E) where V is the set of all vertices in G and E is the set of all edges in G. Graph Theory comes under discrete mathematics which is conducted in 2 part first contains Graph, Theorems, Trees and types, Regular Graph, Edge Connectivity.

This topic is important for various competitive exams such as GATE CE, SSC JE, ISRO, ESE, IES and other computer science exams.

 

 

Graph Notes

  • Isolated Vertex: A vertex with degree zero is called an isolated vertex or lone vertex.
  • Null Graph: A graph with no edges is called a null graph.
  • Simple Graph: A graph with no parallel edges and no loops is called a simple graph.
  • Directed Graph: In a digraph, an edge (u, v) is said to be from u to v.
  • Undirected Graph: In an undirected graph an edge {u, v} is said to join u and v or to be between u and v.
  • Pendant Vertex: A vertex with degree one is called a Pendant vertex.
  • Path: It is the sequence of edges, without vertex repetition.
  • Network: It is a graph with only one source and one sink.
  • Trial (Tour or Walk): It is the sequence of edges without edge repetition (vertex may repeat).
  • Independence Number: Number of vertices in a largest maximal independent set.
  • The diameter of a Graph: Maximum distance between any two vertices in a graph.
  • Loop: An edge is drawn from a vertex to itself.
  • Trivial Graph: A graph with no edges and one vertex.
  • Discrete Graph or Null Graph: A graph with only isolated vertices and no edges.
  • Pseudo Graph: A graph in which self-loops are allowed as well as parallel or multiple edges are allowed.

Hand Shaking Theorem

Graph Theory Discrete Mathematics Study Notes (Part-1)

Tree & Types

Graph Theory Discrete Mathematics Study Notes (Part-1)

Regular Graph

Graph Theory Discrete Mathematics Study Notes (Part-1)

Edge Connectivity

Graph Theory Discrete Mathematics Study Notes (Part-1)

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Related Links

GATE CSE Syllabus 2022

GATE CSE Exam Pattern 2022

GATE CSE Question Papers

GATE CSE Books 2022

GATE CSE Study Plan

GATE CSE Exam Analysis 2022

GATE CSE Answer Key 2022

GATE CSE Result 2021

GATE CSE Counselling

BARC CS Syllabus

BARC CS Study Plan

BARC CS Exam Analysis

Thanks

Prep Smart. Score Better!

Download BYJU’S Exam Prep, Best gate exam app for Preparation

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium