Graphs (undirected, unlabelled, and simple)

Contents

# 1. Definition

A **graph** $G = (V,E)$ consists of

a set $V$ of vertices (which we assume for simplicity to be $\{0,\ldots,n-1\}$) and,

a set $E \subseteq \binom{V}{2}$ of edges.

We consider graphs to be

*undirected*: edges are unordered pairs of vertices,*unlabelled*: graphs $G = (V,E)$ and $G' = (V',E')$ are considered*equal*if there is a permutation $\pi : V \rightarrow V'$ such that $\{u,v\} \in E \Leftrightarrow \{\pi(u),\pi(v)\} \in E'$,*simple*: multiple edges and loops are disallowed.

# 2. Examples

The four (undirected, unlabelled, simple) graphs on three vertices $\{0,1,2\}$ are

$E_1 = \{\}$,

$E_2 = \{\{0,1\}\}$,

$E_3 = \{\{0,1\},\{1,2\}\}$,

$E_4 = \{\{0,1\},\{1,2\},\{0,2\}\}$.

# 3. Further Definitions

If $\{u,v\}$ is an edge in a graph $G$, then $u$ and $v$ are

**adjacent vertices**. $u$ and $v$ are also known as**neighbors**. The set of neighbors of $v$, denoted $N(v)$, is called the**neighborhood**of $v$. The**closed neighborhood**of $v$ is $N[v]=N(v)\cup {v}$.If two edges share a vertex in common (e.g. $\{u,v\}$ and $\{v,w\})$, then they are

**adjacent edges**.The

**degree**of a vertex $v$, denoted**deg($v$)**, is the number of vertices adjacent to $v$.We call $|V(G)|$, the cardinality of the vertices of a graph $G$, the

**order**of the graph. We also say $|E(G)|$, the cardinality of the edges of a graph $G$, is the**size**of the graph.A graph of size 0 is called an

**empty graph**. Any graph with at least one edge is called**nonempty**.A graph is

**complete**when any two distinct vertices are adjacent. The complete graph of $n$ vertices is notated $K_{n}$A

**planar graph**is a graph that can be embedded in the plane. I.e. it can be drawn on the plane such a way that its edges intersect only at their endpoints.A

**walk**$W$ in a graph $G$ is a sequence of vertices in $G$, beginning at a vertex $u$ and ending at a vertex $v$ such that the consecutive vertices in $W$ are adjacent in $G$.A walk whose initial and terminal vertices are distinct is called an

**open walk**, otherwise it is a**closed walk**.A walk in which no edge repeats is called a

**trail**.A

**path**$P$ in a graph $G$ is a sequence of edges which connect a sequence of vertices which, are all distinct from one another. A path can also be thought of as a walk with no repeated vertex.A

**simple path**is one which contains no repeated vertices (in other words, it does not cross over itself).If there is a path from a vertex $u$ to a vertex $v$ then these two vertices are said to be

**connected**. If every two vertices in a graph $G$ are connected, then $G$ is itself a**connected graph.**A nontrivial closed walk in a graph $G$ in which no edge is repeated is a

**circuit**in $G$.A circuit with vertices $v_1, v_2, ..., v_k, v_1$ where $v_2, ..., v_k$ are all distinct is called a

**cycle**.Let $G$ be a nontrivial connected graph. A circuit $C$ of $G$ that contains every edge of $G$ (necessarily exactly once) is called an

**Eularian Circuit**. Any graph which contains an Eularian Circuit is called**Eularian**.

# 4. Properties

## 4.1. Subgraphs

Given graphs $G$ and $H$, $H$ is a *subgraph* of $G$, notated *$H\subseteq G$*, if

$V(H)\subseteq V(G)$

$E(H)\subseteq E(G)$

$H$ is a *proper subgraph* if either

$V(H)\subsetneq V(G)$

$E(H)\subsetneq E(G)$

If $V(H)=V(G)$ but $E(H)\subsetneq E(G)$, then $H$ is a *spanning subgraph* of $G$.

## 4.2. Edge Counting Theorem

If $G$ is a graph of size $m$, then $\sum_{v\in V(G)} deg(v) = 2m$

## 4.3. Eularian Graph Criteria

A nontrivial connected graph $G$ is Eularian if and only if every vertex of G has even degree.

## 4.4. Four Color Theorem

Every planar graph is four-colorable. That is, the chromatic number of a planar graph is at most four.

# 5. Remarks

A *labeled* graph is a graph which has all of its vertices labeled.

A *multigraph* is a graph in which multiple edges between vertices are allowed as well as loops that connect a vertex to itself.

A *directed* graph or digraph is a graph in which each edge has a specific orientation or direction.

We have the following **103 statistics** in the database:

# 6. Maps

We have the following **3 maps** in the database:

# 7. References

G. Chartrand, L. Lesniak, and P. Zhang.

*Graphs and Digraphs.*CRC Press, Oct. 2010.

# 8. Sage examples