01. Introduction

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$

Link to original

Vertex Set

Let $G$ be a graph then

$$V=V(G)$$

is the vertex set of $G$

Link to original

Edge Set

Let $G$ be a graph then

$$E=E(G)$$

is the edge set of $G$

Link to original

Edge

Let $x,y$ be vertices then

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

denotes the edge between $x,y$

Link to original

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}$$

Link to original

Drawing Graphs

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

Link to original

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)$$

Link to original

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)$$

Link to original

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$

Link to original

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$

Link to original

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\}$$

Link to original

Walk

Let $G$ be a graph then

Walk $W$ is sequence

$$v_0{v}_1\cdots v_t\text{ where }{v}_i\in G$$

such that

$$v_i{v}_{i+1}\in E\text{ for all }i=0,1,\cdots ,t-1$$

where length of walk is denoted by number of steps $t$

Note that the vertices don’t have to be necessarily distinct

$x-y$ walk Suppose $x=v_0$ and $y=v_t$ then

Walk from $x$ to $y$ is $x-y$ walk

Link to original

Path

Let $G$ be a graph then

Path in $G$ is a walk where $v_0,\cdots ,v_t$ are distinct

Link to original

Closed Walk

Let walk $W$ be of graph $G$

Walk $W$ is closed if

$$v_t=v_0$$

Link to original

Cycle

Let walk $W$ be of graph $G$ defined by

$$v_1{v}_2\cdots v_t$$

Then $v_1{v}_2\cdots v_t$ is a cycle in $G$ if and only if

1. $t\ge 3$
2. $v_1,\cdots ,v_t$ are distinct vertices of $G$
3. $v_1{v}_2,\cdots ,v_{t-1}{v}_t,v_t{v}_1$ are edges of $G$

Link to original

Acyclic Graph

Let $G$ be a graph then

$G$ is acyclic if it contains no cycles

Link to original

Equivalency of Walks and Paths in Graphs lemma

Let $G$ be a graph
Let $x,y\in V(G)$ then

$G$ contains an $x-y$ walk $⟺$ $G$ contains a $x-y$ path

Proof

Any path is a walk so $⟸$ is trivial

Suppose $G$ contains $x-y$ walk so let

$$v_0\cdots v_t$$

be shortest $x-y$ walk in $G$

If $v_i=v_j$ for some $i<j$ then construct shorter $x-y$ walk

$$v_0\cdots v_i{v}_{j+1}\cdots v_t$$

where if $j=t$ then use $v_0\cdot v_i$

Hence as all vertices in walk are now distinct then it is a path

Link to original

Connected Vertices

Let $G$ be a graph
Let $x,y\in V(G)$

$x,y$ are connected in $G$ if

$$G\text{ contains }x-y\text{ walk / path}$$

Link to original

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$

Link to original

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$

Link to original