Graph Theory Discrete Mathematics Study Notes (Part-1)

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

Tree & Types

Regular Graph

Edge Connectivity

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

Thanks

Prep Smart. Score Better!

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