## Define

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

Edge

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

## Degrees

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

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.

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$$

## Isomorphism

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

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

## Distances

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$

## Connectivity

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: $K_{3,2}$

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

$$\text{edge}=mn$$