A graph $G=(V,E)$ consists of $V$, a nonempty set of vertices (or nodes) and $E$, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

The set of vertices may be infinite.
A graph with an infinite vertex set or with an infinite edges set is called an infinite graph.
A graph with a finite vertex set and a finite edge set is called a finite graph.
We will usually consider only finite graphs.

A simple graph has undirected graphs, no multiple parallel edges and no loops (edges connecting the same vertex to itself).

Let $G=(V,E)$ be an undirected graph.
If $e$ is an edge wwith enpoints $u$ and $v$, we say that:

• $u$ and $v$ are adjacent or neighbors.
• $e$ is incident with $u$ and $v$.
• $e$ connects $u$ and $v$.

• The set of all neighbours of a vertex $v$ is called the $neighbourhood$ if $v$ and is denoted by $N(V).$
• The neighbourhood of a set $A$ of vertices is $N(A):={\cup }_{v\in A}N(v)$
• The degree of a vertex $v$, denoted by $deg(V)$ is the number of edges incident with $v$. Each loop contributes twice to the degree of a vertex.
  • A vertex of degree 0 is isolated.
  • A vertex of degree $1$ is pendant.

(The Handshaking Theorem) Let $G=(V,E)$ be an undirected graph with $m$ edges. Then:

Each vertex's degree counts an edge twice.

An undirected graph has an even number of vertices of odd degree.

This immediately follows from the handshaking theorem.

How many graphs are there on $103$ vertices such that each vertex has degree $7$?

Let $G=(V,E)$ be a directed graph.
If $(u,v)$ is an edge, we say that

• $u$ is adjacent to $v$ and $v$ is adjacent from $u$.
• $u$ is the initial vertex and $v$ is the terminal vertex of $(u,v)$
• $v$ is an out-neighbor of $u$ and $u$ is an in-neighbour of $v$.

The in-degree of a vertex $v$, denoted by $de{g}^{-}(v)$ is the number of edges with $v$ as the terminal vertex.
The out-degree of a vertex $v$, denoted by $de{g}^{+}(v)$ is the number of edges with $v$ as the initial vertex.

(The Handshaking Theorem) Let $G=(V,E)$ be a directed grpah with $m$ edges. Then:

A complete graph on $n$ vertices, denoted by $K_n$ is a simple graph that contains exactly one edge between each pair of distinct vertices.

A cycle $C_n$, $n\ge 3$, consists of $n$ vertices $v_1,v_2,...,v_n$ and edges $\{v_1,v_2\},\{v_2,v_3\},...,\{v_{n-1},v_n\},\{v_n,v_1\}$.

A wheel $W_n$ when we add an additional vertex to a cycle $C_n$, for $n\ge 3$ and connect this new vertex to each of the $n$ vertices in $C_n$ by new edges.

An $n-$dimensional hypercube, or $n-$cube, denoted by $Q_n$, is a graph that has vertices representing the $2^n$ bit strings of length $n$. Two vertices are adjacent if and only if the bit strings they represent differ exactly in one position.

A simple graph $G$ is bipartite if the vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge in the graph connects a vertex $V_1$ and a vertex $V_2$ exclusively. We call such a pair $(V_1,V_2)$ a bipartition of $V$.

• Every even cycle is a bipartite.
• Every hypercube is bipartite.
• $K_3$ is not bipartite

A simple graph is bipartite if and only it is possible to assign two colours to the vertices of the graph in such a way that no two adjacent vertices are assigned the same color.