The document outlines key concepts related to graphs, including definitions, types (directed, undirected, mixed), and specific characteristics such as self loops and parallel edges. It also discusses the order and size of graphs, the degree of vertices, and important results like the Handshaking Lemma. Additionally, it covers the concepts of source and sink vertices and introduces the degree sequence of a graph.
The document outlines key concepts related to graphs, including definitions, types (directed, undirected, mixed), and specific characteristics such as self loops and parallel edges. It also discusses the order and size of graphs, the degree of vertices, and important results like the Handshaking Lemma. Additionally, it covers the concepts of source and sink vertices and introduces the degree sequence of a graph.
The document outlines key concepts related to graphs, including definitions, types (directed, undirected, mixed), and specific characteristics such as self loops and parallel edges. It also discusses the order and size of graphs, the degree of vertices, and important results like the Handshaking Lemma. Additionally, it covers the concepts of source and sink vertices and introduces the degree sequence of a graph.
The document outlines key concepts related to graphs, including definitions, types (directed, undirected, mixed), and specific characteristics such as self loops and parallel edges. It also discusses the order and size of graphs, the degree of vertices, and important results like the Handshaking Lemma. Additionally, it covers the concepts of source and sink vertices and introduces the degree sequence of a graph.
be connected if they are connected by an edge. TYPES OF GRAPHS
Directed Graphs
A graph in which every edge is directed is called directed graph or digraph.
Every edge in a directed graph is directed.
TYPES OF GRAPHS (ctd…)
Undirected Graphs
A graph in which every edge is undirected is called undirected graph. TYPES OF GRAPHS (ctd…)
Mixed Graphs
A mixed graph in which both directed and undirected edges may exist. TYPES OF GRAPHS (ctd…)
Self Loops
A self loop is an edge
that connects a vertex to itself. TYPES OF GRAPHS (ctd…)
Parallel/ Multiple Edge
Multiple edges (also
called parallel edges or a multi- edge), are two or more edges that are incident to the same two vertices. SIMPLE GRAPH
A graph without loops and parallel edges.
NULL GRAPH
A null graph is a graph in which there are no
edges between its vertices. A null graph is also called empty graph. TRIVIAL GRAPH
A trivial graph is the graph which has only one vertex.
ORDER & SIZE OF GRAPH
The number of vertices denoted by 𝑽 𝑮 is called order of G.
Order = 4 Size = 3
The number of edges denoted by 𝑬 𝑮 is called size of G.
DEGREE of VERTEX
It is the number of edges incident on a vertex.
The degree of vertex a is written as deg(a)
deg(a) = 2
deg(b) = 2
deg(c) = 3
deg(d) = 1
If the degree of vertex a is 0 then it is called isolated vertex.
If the degree of vertex a is 1 then it is called pendent vertex. DEGREE of VERTEX in a UNDIRECTED GRAPH
An undirected graph has no directed edges.
DEGREE of VERTEX in a DIRECTED GRAPH DEGREE of VERTEX in a DIRECTED GRAPH (ctd…)
Degree of vertex V = Indegree of vertex V + Outdegree of vertex V
Sum of outdegree of vertices = Sum of indegree of vertices = Number of edges
SOURCE & SINK
A vertex A vertex V V with with zero zero outdegree indegree is called is called sink source Some RESULTS
RESULT 1
The sum of the degrees of the vertices of a graph G is
equal to twice the number of edges in G.
deg v = 2|E|
This is also known as Handshaking Lemma
Some RESULTS (ctd…)
RESULT 2
In any graph, the number of vertices of odd degree is even.
RESULT 3
The maximum degree of any vertex in a simple graph with n
vertices is n-1. Some RESULTS (ctd…)
RESULT 4
The maximum number of edges in a graph with n
𝑛(𝑛−1) vertices and no multiple edges are 2 DEGREE SEQUENCE
Degree sequence of a graph is the list of degree of all the vertices of the graph. Usually we list the degrees in non increasing order, that is from largest degree to smallest degree.
