Basics of Graphs

Undirected Graphs

(Undirected) Graph

A (undirected) graph is an ordered pair $G=(V,E)$ where $V$ is a set whose elements are called vertices or nodes. $E$ is a set of pairs of vertices, called arcs or edges.
An empty graph is a graph that has en empty set of vertices.

Order and Size

The order of a graph is the number of vertices it has, and the size of a graph is the number of edges it has.

Directed Graphs

Directed Graph

A directed graph, also called a digraph, is a graph $G=(V,E)$ in which the edges have a direction. That is $E$ is a set of ordered pairs of vertices, called directed edges.
A digraph thus consists of two functions, source $s:E\to V$ and target $t:E\to V$.

Path

A path is a finite sequence of edges $e_1,\dots ,e_n$ in a graph such that $t(e_i)=s(e_{i+1})$ for all $i=1,2,\dots ,n-1$.

Def Directed Graph Homomorphism
Directed graph homomorphism is a mapping of edges to edges and vertices to vertices that preserves sources and targets.