01 - Graphs

Graph

Ordered Pair

$$(V,E)$$

where

1. Vertices $V$ of $G$, is a non-finite set
2. Edges $E$ of $G$ is the set of $2$-element subsets of $V$

Vertex Set

Let $G$ be a graph then

$$V=V(G)$$

is the vertex set of $G$

Edge Set

Let $G$ be a graph then

$$E=E(G)$$

is the edge set of $G$

Edge

Let $x,y$ be vertices then

$$xy\text{ or }\{x,y\}$$

denotes the edge between $x,y$

Adjacent / Neighbours

Let $x,y$ be vertices of $G$ then

$x$ and $y$ are adjacent in $G$ (or neighbours) if

$$xy\text{ is an edge of G}$$

Drawing Graphs

Vertices denoted as blobs
Edges denoted as lines between vertices (ensuring edges don’t intersect)

Isomorphism of Graphs

Let $G,H$ be graphs

$G$ and $H$ are isomorphic if

$$\exists \text{ bijection }\phi :V(G)\to V(H)$$

such that for all $x,y\in V(g)$ then

$$xy\in E(G)⟺\phi (x)\phi (y)\in E(H)$$

Subgraphs

Let $G,H$ be a graph then

$H$ is a subgraph of $G$ if

$$V(H)\subseteq V(G)\text{ and }E(H)\subseteq E(G)$$

Removing Edge from Graph

Let $G$ be a graph with edge $e\in E(G)$

$G-e$ denotes subgraph

$$(V,E\setminus \{e\})$$

where edge $e$ is deleted from $G$

Removing Vertex from Graph

Let $G$ be a graph with vertex $v\in V(G)$

$G-v$ denotes subgraph
where $v$ and all edges incident with $v$

Examples of Graphs

Complete Graph

Complete Graph of $n$ vertices is $K_n$ with

$$V=\{1,2,\cdots ,n\}$$

and $E$ the set of all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges

Empty Graph

Empty Graph of $n$ vertices is $E_n$ for $n\ge 1$ with
$n$ vertices and $0$ edges

Path

Path of Length $n$ for $n\ge 0$ with

$$V=\{0,1,\cdots ,n\}\text{ and }E=\{01,12,\cdots ,(n-1)n\}$$

where path of length of $n$ has $n+1$ vertices and $n$ edges

Note that it can be denoted as $P_n$ or $P_{n+1}$

Cycle

Cycle of length $n$ is $C_n$ for $n\ge 3$ with

$$V=\{1,2,\cdots ,n\}\text{ and }E=\{12,23,\cdots ,(n-1)n,n1\}$$

Acyclic Graph

Let $G$ be a graph then

$G$ is acyclic if it contains no cycles

Connected Graph

Let $G$ be a graph then

$G$ is connected if for all $x,y\in V(G)$ then $x,y$ are connected in $G$

Equivalence Relation for Graphs

Let $G$ be a graph then

$x\sim y$ if $x$ and $y$ are connected in $G$ is an equivalence relation where
Equivalence class partition $V(G)$ into disjoint connected subgraphs called components of $G$

Minimal Connected Graph

Let $G$ be a graph then

$G$ is a Minimal Connected Graph if

1. $G$ is connected
2. $G-e$ is not connected for all $e\in E(G)$

Note that it means every edge is required for connectivity

Neighbourhood of a Vertex

Let $G=(V,E)$ be a graph with $v\in V$ then

Neighbourhood of $v$ is

$$\Gamma (v)={\Gamma }_G(v)=\{w\in V:vw\in E\}$$

Degree of a Vertex

Let $G=(V,E)$ be a graph with $v\in V$ then

Degree of vertex $v$ is

$$d(v)=d_G(v)=|\Gamma (v)|$$

Leaf of Graph

Let $G$ be a graph then

$v$ is a leaf of $G$ if

$$d(v)=1$$

Number of Vertices of $G$

Let $G$ be a graph then

$$|G|\equiv v(G)\equiv |V(G)|$$

is the number of vertices of $G$

Number of Edges of $G$

Let $G$ be a graph then

$$e(G)\equiv |E(G)|$$

is the number of edges of $G$

Number of edges when Removing Vertex of Graph

Let $G$ be a graph with $v\in V(G)$ then

$$e(G-v)=e(G)-d(v)$$

Spanning Subgraph

Let $G$ be a graph
Let $H$ be a subgraph of $G$ then

$H$ is a spanning subgraph of $G$ if

$$V(H)=V(G)$$

Adding Edges to a Graph

Let $G$ be a graph
Let $e$ be a edge then

$G+e$ is the graph formed from $G$ and adding edge $e$

Notation

Suppose $G=(V,E)$ then

$$G+e=(V,E\cup \{e\})$$

where $e=xy$ for $x\ne y$ and $e\notin E(G)$

Maximal Acyclic Graph

Let $G$ be acyclic graph then

$G$ is maximal acyclic if there does not exist $e$ such that $G+e$ is acyclic

Cyclic Property of Adding Edge to Graph

Let $G$ be a graph

Adding edge $e=xy$ to graph $G$ creates cycle $⟺$ $H$ contains $x$-$y$ path

Isolated Vertex

Let $G$ be a graph with vertex $v$ then

$v$ is a Isolated Vertex if

$$d_G(v)=0$$

Eulerian Graph

Let $G$ be a graph then

$G$ is a Eulerian Graph if all vertices has even degree