Graphs

Graphs

A graph $G=(V,E)$ contains of a non-empty set $V$ of vertices and a set $E$ of edges

An edge must connects to two neighbors

Edges

Directed edge $e=\left\{u,v\right\}$
Undirected edge $e=\left(u,v\right)$

Degrees

If an undirected graph has $m$ edges, then

$$2m=\sum _{v\in V}\mathrm{deg}(v)$$

If a directed graph has $m$ has $m$ edges, then

$$m=\sum _{v\in V}{\mathrm{deg}}^{-}(v)=\sum _{v\in V}{\mathrm{deg}}^{+}(v)$$

Types of Graphs

Simple Graphs

A undirected graph without loops and multiple edges

Bipartite Graphs

A simple graph that can be partitioned into two disjoint subsets such that every edge connects between those two sets

Complete Bipartite Graphs

A simple graph that be partitioned into two disjoint subsets such that there is an edge from every vertex in $V_1$ to every vertex in $V_2$

Graph Isomorphism

Can be shown by a bijection function

Euler Circuits

An undirected connected graph has an Euler circuit $⟺$ all vertices have even degrees

Euler Paths

An undirected connected graph has an Euler path but not an Euler circuit $⟺$ there are exactly two vertices of odd degree