\section{Basic Definitions}
\begin{flushleft}
\textbf{Graph}:
\end{flushleft}
A \textbf{graph} G consists of a set V of \textbf{vertices} and a collection E
(not necessarily a set) of unordered pair of vertices called \textbf{edges}.A graph
G is symbolically represented as G(V,E).
\begin{flushleft}
\textbf{Order of a Graph}:
\end{flushleft}
The order of a graph is its number of vertices.
\begin{flushleft}
\textbf{Size of a Graph}:
\end{flushleft}
The size of a graph is its number of edges.
\begin{flushleft}
\textbf{Parallel Edges}:
\end{flushleft}
Two or more edges that join the same pair of distinct vertices are called parallel
or multiple edges.
\begin{flushleft}
\textbf{Loop}:
\end{flushleft}
An edge represented by an unordered pair in which the two elements are not distinct
is known as a loop.
\begin{flushleft}
\textbf{Pendant Vertex}:
\end{flushleft}
A pendant vertex is a vertex that is connected to exactly one other vertex by a
single edge.
\begin{flushleft}
\textbf{Walk}:
\end{flushleft}
A walk in a graph is a sequence of alternating vertices and edges
$v_{1}e_{1}v_{2}e_{2}...v_{n}e_{n}v_{n+1}$ with n $\geqslant0$. If
$v_{1}=v_{n+1}$then the walk is closed. The length of the walk is the number of
edges in the walk.
\begin{flushleft}
\textbf{Trivial Walk}:
\end{flushleft}
A walk of length zero is a\textbf{ trivia}l walk.
A trail is a walk with no repeated edges.
\begin{flushleft}
\textbf{Path}:
\end{flushleft}
A path is a walk with no repeated vertices.
\begin{flushleft}
\textbf{Circuit}:
\end{flushleft}
A circuit is a closed trail and a trivial circuit has a single vertex and no
edges.
\begin{flushleft}
\textbf{Eulerian Trail/Circuit}:
\end{flushleft}
A trail or circuit is Eulerian if it uses every edge in the graph.
\begin{flushleft}
\textbf{Cycle}:
\end{flushleft}
A cycle is a nontrivial circuit in which the only repeated vertex is the
first/last
one.
\begin{flushleft}
\textbf{Degree of a Vertex}:
\end{flushleft}
The degree of a vertex is the number of edges incident to the vertex and is
denoted deg(v).
\begin{flushleft}
\textbf{In-Degree and Out-Degree of a Vertex}:
\end{flushleft}
In a directed graph, the in-degree of a vertex is the number of edges incident to
the vertex and the out-degree of a vertex is the number of edges incident from the
vertex.
\begin{flushleft}
\textbf{Subgraph}:
\end{flushleft}
A graph H is a subgraph of a graph G if all vertices and edges in H arealso in G.
\begin{flushleft}
\textbf{Connected Component of Graph}:
\end{flushleft}
A connected component of G is a connected subgraph H of G such that no other
connected subgraph of G contains H.
\newpage
\section{Types Of Graphs}
\begin{flushleft}
\textbf{Null Graph}:
\end{flushleft}
A null graph is a graph in which there are no edges between its vertices. A null
graph is also called empty graph.
\begin{flushleft}
\textbf{Trivial Graph}:
\end{flushleft}
A trivial graph is the graph which has only one vertex.
\begin{flushleft}
\textbf{Simple Graph}:
\end{flushleft}
A simple graph is the undirected graph with no parallel edges and no loops.A
simple graph which has n vertices, the degree of every vertex is at most n -1.
\begin{flushleft}
\textbf{Multi-Graphs}:
\end{flushleft}
A graph in which there are multiple edges between any pair of vertices or there
are edges from a vertex to itself (loop) is called a multi - graph.
\begin{flushleft}
\textbf{Directed Graph}:
\end{flushleft}
A directed graph is a graph in which the edges may only be traversed in one
direction. Edges in a simple directed graph may be specified by an ordered pair $
(v_{i}, v_{j} )$ of the two vertices that the edge connects. We say that $v_{i}$ is
\textbf{adjacent to} $v_{j}$ and $v_{j}$ is \textbf{adjacent from} $v_{i}$
\begin{flushleft}
\textbf{Undirected Graphs}:
\end{flushleft}
An undirected graph is a graph whose edges are not directed.
\begin{flushleft}
\textbf{Connected Graph}:
\end{flushleft}
A graph is connected if there is a walk between every pair of distinct vertices in
the graph.
\begin{flushleft}
\textbf{Disconnected Graphs}:
\end{flushleft}
A disconnected graph is a graph in which any path does not exist between every
pair of vertices.
\\\begin{flushleft}
\textbf{Complete Graph}:
\end{flushleft}
The complete graph of n nodes, denoted $K_{n}$, is the simple graph with node \
{1,...n\} and an edge between every pair of distinct nodes.
\begin{flushleft}
\textbf{Regular Graphs}:
\end{flushleft}
A Regular graph is a graph in which degree of all the vertices is same.
\begin{flushleft}
\textbf{Cyclic Graphs}:
\end{flushleft}
A graph with \textbf{n} vertices (where, n$\geqslant3$) and \textbf{n} edges
forming a cycle of \textbf{n} with all its edges is known as cycle graph.
A graph containing at least one cycle in it is known as a cyclic graph.
In the cycle graph, degree of each vertex is 2.
The cycle graph which has n vertices is denoted by $C_{n}$.
\begin{flushleft}
\textbf{Acyclic Grsphs}:
\end{flushleft}
A graph which does not contain any cycle in it is called as an acyclic graph.
\begin{flushleft}
\textbf{Star Graphs}:
\end{flushleft}
A star graph is a complete bipartite graph in which n-1 vertices have degree 1 and
a single vertex have degree (n -1). This exactly looks like a star where (n - 1)
vertices are connected to a single central vertex.
A star graph with n vertices is denoted by $S_{n}$.
\begin{flushleft}
\textbf{Eulerian Graph}:
\end{flushleft}
A graph is called Eulerian if it contains an Eulerian circuit.
\begin{flushleft}
\textbf{Tree Graph}:
\end{flushleft}
A tree is a connected, simple graph that has no cycles. Vertices of degree 1 in
a tree are called the \textbf{leaves} of the tree.
\begin{flushleft}
\textbf{Spanning Tree}:
\end{flushleft}
Let G be a simple, connected graph. The subgraph T is a spanning tree of G if T is
a tree and every node in G is a node in T.
\begin{flushleft}
\textbf{Weighted Graph}:
\end{flushleft}
A weighted graph is a graph G = (V, E) along with a function w : E → R that
associates a numerical weight to each edge. If G is a weighted graph, then T is a
\textbf{minimal spanning tree} of G if it is a spanning tree and no other spanning
tree of G has smaller total weight.
\begin{flushleft}
\textbf{Bipartite Graph}:
\end{flushleft}
A graph is called bipartite if its set of nodes can be partitioned into two
disjoint sets \textbf{S1}
and \textbf{S2} so that every edge in the graph has one endpoint in S1 and one
endpoint in S2.
\begin{flushleft}
\textbf{Complete Bipartite Graph}:
\end{flushleft}
The complete bipartite graph on n, m nodes, denoted $K_{n,m}$, is the simple
bipartite graph with nodes S1 = \{a1, . . . , an\} and S2 =\{b1, . . . , bm\} and
with edges connecting each node in S1 to every node in S2.
\begin{flushleft}
\textbf{Isomorphic Graphs}:
\end{flushleft}
Simple graphs G and H are called isomorphic if there is a bijection f from the
nodes of G to the nodes of H such that \{v,w\} is an edge in G if and only if \
{f(v), f(w)\}is an edge of H. The function f is called an \textbf{isomorphism}.
\begin{flushleft}
\textbf{Planar Graphs}:
\end{flushleft}
A simple, connected graph is called planar if there is a way to draw it on a plane
so that no edges cross. Such a drawing is called an \textbf{embedding} of the graph
in the plane.
\begin{flushleft}
\textbf{Non-Planar Graphs}:
\end{flushleft}
A graph that is not a planar graph is called a non-planar graph. In other words, a
graph that cannot be drawn without at least on pair of its crossing edges is known
as non-planar graph.
\\
\section{Basic Theorems}
\begin{flushleft}
\textbf{Theorem 01}:
\end{flushleft}
Let G be a connected graph. Then G is Eulerian if and only if every vertex in G
has even degree.
\begin{flushleft}
\textbf{Theorem 02(Handshaking Lemma)}:
\end{flushleft}
In any graph with n vertices $v_{i}$ and m edges
\begin{equation}
\sum_{i=1}^{n}deg(v_{i})=2m
\end{equation}
\begin{flushleft}
\textbf{Corollary}:
\end{flushleft}
A connected non-Eulerian graph has an Eulerian trail if and only if it has
exactly two vertices of odd degree. The trail begins and ends these two vertices.
\begin{flushleft}
\textbf{Theorem 03}:
\end{flushleft}
An undirected graph has an even number of
vertices of odd degree.
\begin{flushleft}
\textbf{Theorem 04}:
\end{flushleft}
If T is a tree with n edges, then T has n + 1 vertices.
\begin{flushleft}
\textbf{ Theorem 05}:
\end{flushleft}
Two graphs that are isomorphic to one another must have
\\(1) The same number of nodes.
\\(2) The same number of edges.
\\(3) The same number of nodes of any given degree.
\\(4) The same number of cycles.
\\(5) The same number of cycles of any given size.
\begin{flushleft}
\textbf{Theorem 06(Kuratowski’s Theorem)}: \end{flushleft}
A graph G is nonplanar if and only if it contains a “copy” of $K_{3,3}$ or
$K_{5}$ as a subgraph.