A graph consists of a set of nodes V and a set of edges E.

  • Each edge in E joins two nodes in V
  • Two nodes connected by an edge are called neighbors or adjacent


  1. undirected: can be traversed in both directions
  2. {x,y}, edge xy: When there is only one edge connecting two nodes x and y

simple graph

the graph which has neither multiple edges nor loop edges


the degree of a node v is the number of edges which have v as an endpoint. Represent by Deg(v)

  • if self loop, count twice


For example, deg(a) = 2, deg(b) = 6, deg(d) = 0

The relation between edge number and degree is

$$ \sum_{v\in V}deg(v)=2|E| $$

Type of graph

Several special types of graphs that are useful

1. Complete graph

every node is connected to every other node,l represent by $K_i$ where i represent the node number

complete graph
complete graph

the above complete graph is $K_5$

the edge of it equal to:

$$ \text{edge} = \frac{n(n-1)}{2} $$

2. Cycle graphs

all nodes and edges connecting vi to vi+1, plus an additional edge from vn to v1. where as v represent each single nodes in the graph.

cycle graph
cycle graph

the above cycle graph is $C_5$

$$ \text{edge}= n $$

  • the cycle graph $C_n$ contains 2n different cycles (different start)

3. Wheel

cycle + an external hub, represent by $W_i$ where i is the node number - 1


the above wheel represent by $W_5$
  • $W_n$ has $n+1$ node

$$ \text{egde}=2n $$


Suppose $G(V_1,E_1)$ and $G_2(V_2,E_2)$ are graphs, an isomorphism means $G_1$ to $G_2$ is a bijection $f : V_1 \to V_2$

if there is an isomorphism from $G_1$ to $G_2$, then, we can say they are isomorphic


the above graph is isomorphic because we can map 1 to d, 2 to a, 3 to c and 4 to d
  • isomorphism is another example of an equivalence relation

Check NOT isomorphism:

If not satisfied:

  • same number of nodes and the same number of edges.
  • same number of nodes of degree k

If the two property are identical, we should notice on their subspace. If two graphs G and F are isomorphic, then any subgraph of G must have a matching subgraph somewhere in F.

Subspace: If G and G′ are graphs, then G′ is a subgraph of G if and only if the nodes of G′ are a subset of the nodes of G and the edges of G′ are a subset of the edges of G

not isomorphism
not isomorphism

the left graph has $C_3$ as a subspace but right graph does not.

Walks, paths, and cycles

Walk: sequence of node or edge from one node to another node

  • shortest walk is zero (single node)
  • the walk is closed if its start and end are the same, otherwise it's open
  • can be more than one

Path: a walk in which no node is used more than once

  • cycle is a closed walk with at least three nodes in which no node is used more than once except that the starting and ending nodes are the same
  • cycle diff from close walk that close walk can re-use node
  • acyclic means does not contain cycle in graph
  • can create a path between the nodes by pruning unnecessary loops from the walk.
  • can be more than one


distance from a to b means the length of the shortest path from a to b

  • diameter of a graph is the max distance between any pairs of nodes


diameter above is 4 since $d(f,e)=4$


A graph G is connected if there is a walk between every pair of nodes in G


Not connected because no walk from a to g

connected components: some subset in a graph that each contains a maximal set of nodes that are all connected to one another. The graph above has three connected components

cut edge: if a connected graph become disconnected by removing a single edge, this edge is cut edge

Euler circuits

a closed walk that uses each edge of the graph exactly once

Check is Euler circuits

  • the graph is connected
  • each node has even degree

Bipartite graphs

A graph G = (V, E) is bipartite if we can split V into two non-overlapping subsets V1 and V2 such that every edge in G connects an element of V1 with an element of V2


all R and all G nodes in this graph is not connected with themselves, but connect with each other,o so, it is bipartite graph

Complete bipartite graph:

  • bipartite graph + each subsets are completed connected
  • represent by $K_{m,n}$ where m and n represent node in each subsets

complete bipartite graph
complete bipartite graph

complete bipartite graph: $K_{3,2}$

$$ \text{node}=m+n $$

$$ \text{edge}=mn $$