Major Application of Graph includes *Maps, Hypertext, Circuits, Schedules, Transactions, Matching, Networks, Program Structure(Compiler).*

* Definition :* A

We denote the number of vertices in a given graph by $V$ and number of edges by $E$.

Above definition puts two restrictions on graphs

- Disallow duplicate edges (
*Parallel edges, and a graph that contains them multigraph*) - Disallows edges that connect to itself (
*Self-Loops*)

**Property 1:***A graph with $V$ vertices has at most $V(V-1)/2$ edges.*

We use *vertex* when discussing graphs and *nodes* when discussing representation. We use *edge* when discussing graphs and *links* while discussing C++ data structures but mathematician/books might refer to mean same.

When there is a edge connecting two vertices, we say that the vertices are *adjacent* to one another and edges *incident* on it. The *degree* of vertex is number of edges incident on it. $v-w$ represents edge from $v$ to $w$ and $w-v$ represents edge from $w$ to $v$.

A *subgraph* is a subset of graph’s edges (and associated vertices) that constitutes a graph.

A drawing gives us intuition about the structure of graph but this intuition can be misleading, because graph is defined independently of the representation.

**Same graph represented 3-ways**

A graph is defined by its vertices and its edges, not the way that we choose to draw it.

A *planar graph* is one that can be drawn in the plane without any edges crossing. Figuring out whether a graph is planar or not is a fascinating problem itself. For some graphs drawing can carry information like vertices corresponding points on plane and distance represented by edges are called as *Euclidean graphs.*

Two graphs are *isomorphic* if we can change the vertex labels on one to make its set of edges identical to the other. (Difficult Computation Problem since there are $V!$ possibilities).

**Definition : 2** *A path in a graph is a sequence of vertices in which each successive vertex(after the first) is adjacent to its predecessor in the path.* In a

Sometimes we refer *cyclic paths* to refer to a path whose first and last vertices are same; and we use term *tour* to refer to a cyclic path that includes every vertex.

Two simple paths are *disjoint* if they have non vertices in common other than, possibly, their endpoints.

**Definition 3:** A graph is * connected graph* if there is a path from every vertex to every other vertex in the graph. A graph that is not connected consists of a set of

**Definition 4 :** A acyclic connected graph is called a **tree**. A set of trees is called a **forest**. A **spanning tree** of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree.

A **spanning forest** of a graph is a subgraph that contains all of that graph’s vertices and is a forest.

A graph $G$ with $V$ vertices is a tree if and only if it satisfies any of the following four conditions.

- $G$ has $V-1$ edges and no cycles.
- $G$ has $V-1$ edges and is connected
- Exactly one simple path connects each pair of vertices in $G$
- $G$ is connected, but removing any edge disconnects it

Graphs with all edges present are called *complete graphs.*

*Complement of a graph $G$ has same set of vertices as complete graph but removing the edges of $G$*.

Total number of graphs with $V$ vertices is $2^{V(V-1)/2}$. A complete subgraph is called a *clique*.

*density* of graph is average vertex degree or $\frac{2E}{V}$. A *dense graph* is a graph whose density is proportional to $V$. A *sparse graph* is a graph whose complement is dense.

A graphs is dense if $E \propto V^2$ and sparse otherwise.

Density of graphs helps us choose a efficient algorithm for processing the graph.

When analysing graph algorithms, we assume $\frac V E$ is bounded above by a small constant, so we can abbreviate expression such as $V(V+E)\approx VE$.

A *bipartite graph* is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set. Its quite useful in matching problem. Any subgraph of bipartite graph is bipartite.

Graphs defined above are all *undirected graphs*. In *directed graphs*, also know as *digraphs*, edges are one-way. pair of vertices are in form of ordered pairs.

First vertex in digraph is called as *source* and final vertex is called as *destination*.

We speak of *indegree and outdegree* of a vertex ( the #edges where it is destination and #edges where it is source respectively)

A *directed cycle* in a digraph is a cycle in which all adjacent vertex pairs appear in the order indicated by (directed) graph edges

A *directed acyclic graph (DAG)* is digraph that has no directed cycles.

In *weighted graphs we associate numbers (weights) with each edge, denoting cost or distance.*