Session 02 - Introduction to Graph Theory II

#math

Definition

A graph $G = (V, E)$ is a subgraph of a graph $G^{'} = (V^{'}, E^{'})$ if $V \subseteq V^{'}$ and $E \subseteq E^{'}$ .
A subgraph $G$ of $G^{'}$ is a proper subgraph if $G \neq G^{'}$

Pasted image 20240913102349.png

An example of a subgraph.

Definition

Let $G = (V, E)$ be a simple graph. The subgraph induced by a subset $W$ of the vertex set $V$ is the graph $(W, E^{'})$ where the edge set $E$ contains an edge in $E$ if and only if both endpoints of the edge are in the subset $W$ .

Some Operations on Graphs

Let $G = (V, E)$

removing an edge $e \in E$ is notated by $G - e = (V, E - {e})$
removing a set of edges $E^{'} \subset E$ is notated by $G - E^{'} = (V, E - E^{'})$
adding an edge e is notated by $G + e = (V, E U {e})$
removing a vertex $v$ (and all edges incident to it): $G - v = (V - {v}, E^{'})$ where $E^{'}$ is the set of edges in $E$ not incident to $v$ .
removing a set of vertices $V^{'} \subset V$ : $G - V^{'} = (V - V^{'}, E^{'})$ where $E^{'}$ is the set of edges in $E$ not incident to any vertex in $V^{'}$ .
For an edge $e$ with endpoints $u$ and $v$ , let
$G^{'} = (V^{'}, E^{'})$
$V^{'} = V - {u, v} \cup {w}$
$E^{'}$ = all edges in $E$ that do not have $u$ or $v$ as an endpoint and an edge connecting $w$ with every neighbour of $u$ or $v$ .
The union of $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ is defined to be: $G = (V_{1} \cup V_{2}, E_{1} \cup E_{2})$

Definition

Two simple graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ are isomorphic if there exists a bijection $f : V_{1} \to V_{2}$ such that for all $a, b \in V_{1}$ , $a$ and $b$ are adjacent in $G_{1}$ if and only if if $f (a)$ and $f (b)$ are adjacent in $G_{2}$ .
Such a function $f$ is called an isomorphism.
Two simple graphs are not isomorphic are called nonisomorphic.

Definition

Let $G = (V, E)$ be an undirected graph, and let $n i n N$ .
A path of length $n$ from $u$ to $v$ in $G$ is a sequence of $n$ edges $e_{1}, . . ., e_{n}$ of $G$ which there exists a sequence $x_{0} = u, x_{1}, . . ., x_{n - 1}, x_{n} = v$ of vertices such that $e_{1}$ has, for $i = 1, . ., n$ the endpoints $x_{i - 1}$ and $x_{i}$
The path is a circuit if it begins and ends at the same vertex.
The path passes through the vertices $x_{1}, x_{2}, . . ., x_{n - 1}$ or traverses the edges $e_{1}, . . ., e_{n}$
A path or circuit is simple if it does not contain the same edge more than once.

Definition

An undirected graph is connected if there is a path between every pair of distinct vertices of the graph.