# Graph Theory

Graph Theory is a branch of mathematics that is concerned with the study of graphs. In the case of graph theory, a graph is defined as a collection of vertices connected via edges.

## Definition of Graph

A graph is an ordered pair $G=(V, E)$ where $V$ represents a set of vertices or nodes and $E$ represents a list of pairs say $(x,y)$ where $x,y$ are elements of $V$.

**Example 1**

In the above example, the black lines represent the edges of the graph while the blue circles with labels A to E represent the nodes. The graph can also be represented in mathematical notation as follows:

### Terminologies

**Edge**: An edge is the line or the link between any two vertices of the graph.**Vertex**: A vertex or node is a point or location that can be connected via edges.**Walk**: A walk is an alternating sequence of edges and vertices in which both edges and vertices can be repeated.**Trail**: A trail is a walk in which edges are not repeated.**Path**: A path is a walk in which both edges and vertices are not repeated.**Cycle**: A cycle is a walk in which the starting and ending vertex are the same but the edges and vertices in between are unique and don't repeat.**Loop**: A loop is an edge with the same starting and ending vertex. In example 1, $A\leftrightarrow A$ is a loop.**Weight of an Edge**: Any extra properties assigned to an edge are called its weight. Weight can be length, duration or any other measurable quantity or quantities. Weights are represented as a label for the edge.

## Types of Graphs

### Directed Graph

A graph in which the edges have direction is called a directed graph. For directed graphs, edge $(A, B)$ is not the same as $(B, A)$. A real-world example of a directed graph is cities connected by one-way roads. An example of a directed graph is as follows:

**Example 2**

### Undirected Graph

A graph in which the edges don't have direction is called an undirected graph. For undirected graphs, edge $(A, B)$ is the same as $(B, A)$. In other words, all the edges are bi-directional for undirected graphs. A real-world example of an undirected graph is cities connected by only two-way roads. An example of an undirected graph is as follows:

**Example 3**

### Connected Graph

A graph that has at least one path between every pair of vertices is called a connected graph. For example:

### Disconnected Graph

A graph that doesn't have any path between one or more pairs of vertices is called a disconnected graph. Following is an example of a disconnected graph as we can't reach from vertex A to D.

### Weighted Graph

Graphs whose edges have a weight associated with them are called weighted graphs. In the real world, most graphs are weighted, if we take the example of cities connected by roads as a graph, the length of the roads, the traffic congestion etc act as the weight for the edge. A weighted graph may be represented as follows, the weight is generally represented as a label for the edge.

### Unweighted Graph

A graph in which all the edges don't have any weight is called an unweighted graph. An unweighted graph can also be supposed as a graph in which all the edges have equal weight so that any walk with an equal number of edges has the same cost.

### Null Graph

An edgeless graph is called a null graph. Null graphs may or may not have vertices.

### Simple Graph

An undirected, unweighted graph without any loops and multiple edges between any two nodes, is called a simple graph. A simple graph may or may not have cycles. Example:

### Multi Graph

A graph that may have multiple edges between any two nodes and/or loops is called a multi graph. Example:

### Complete Graph

A graph in which each vertex is connected to every other vertex is called a complete graph. Example:

### Planar Graph

A graph that can be drawn in a plane without any intersecting edges is called a planar graph.