Graph
A graph G=(V,E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.
Types of Graphs
Directed Graphs
A directed graph (or digraph) (V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.
Undirected Graph
All edges are bidirectional. If vertex A is connected to vertex B, then B is also connected to A.
Weighted Graph
Each edge has an associated weight, which could represent a cost, distance, or any other metric.
Unweighted Graph
All edges are treated equally without any weights or costs.
Graph Terminologies
Degree of a Vertex
Neighbourhood
Isolated Vertex
Pendant Vertex
In-degree Vertex
Out-degree Vertex
Example - 1
In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1, deg(e) = 3, and deg(g) = 0. The neighborhoods of these vertices are N(a)={b,f}, N(b)={a,c,e,f}, N(c)={b,d,e,f}, N(d)={c}, N(e)={b,c,f}, N(f)={a,b,c,e}, and N(g)=∅. In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d) = 5. The neighborhoods of these vertices are N(a)={b,d,e}, N(b)={a,b,c,d,e}, N(c)={b}, N(d)={a,b,e}, and N(e)={a,b,d}
Example-2
$$ $$ The in-degrees in graph ( G ) are as follows: $$ \deg^-(a) = 2, \quad \deg^-(b) = 2, \quad \deg^-(c) = 3, \quad \deg^-(d) = 2, \quad \deg^-(e) = 3, \quad \deg^-(f) = 0 $$ The out-degrees are as follows: $$\deg^+(a) = 4, \quad \deg^+(b) = 1, \quad \deg^+(c) = 2, \quad \deg^+(d) = 2, \quad \deg^+(e) = 3, \quad \deg^+(f) = 0$$
Handshaking Theorem
References:
[1] DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION