📂Graph Theory

Graphical Set Notation

Definition ¹

Let’s consider two graphs $G_{1}$ and $G_{2}$ and let $V(G_{1}) \cap V(G_{2}) = \emptyset$.

1. The union $G = G_{1} \cup G_{2}$ of two graphs is a graph that has a vertex set $V(G_{1}) \cup V(G_{2})$ and an edge set $E (G_{1}) \cup E ( G_{2} )$.
2. If graph $H$ cannot be represented as the union of other graphs, then $H$ is said to be connected; otherwise, it is disconnected.
3. Each connected graph within a disconnected graph is called a component.
4. Especially, if the graph becomes disconnected by the removal of edge $b \in G$, then $b$ is called a bridge.

Description

These definitions are similar to the way connectivity is defined in topology.

Although connectivity, as purely defined in graph theory, seems like an important topic, ironically, since disconnected components can be completely treated separately, it is enough to consider connected graphs only. It’s not that connectivity isn’t important, but usually, for research purposes, there’s no need to think about disconnected cases.

Connectivity becomes an important issue when dealing with analysis reflecting real data or applied network theory involving random networks. Whether a random network is surely a connected graph or not is a significant issue in various simulations. Consider a case where the connectivity of the network is not guaranteed. Isolated nodes are mostly ineffective in most mathematical models, and even without isolated nodes, a disaster may occur where only a part of the network is considered while the rest is discarded.

Theorem ²

Let’s assume that a simple graph $G$ has $n$ vertices. If $G$ has $k$ components, then the number of edges $m$ of $G$ satisfies the following. $$ n-k \le m \le (n-k)(n-k+1)/2 $$

Proof

Part 1. $n-k \le m$

When $G$ is a null graph, $n=k$ and thus $m=0$, so $ n-k = 0 \le 0 = m$ holds.

Assume that $n - k \ge m$ holds when $G$ has $k$ components. Let’s define the minimum number of edges required for $G$ to have $k$ components as $m_{0}$. Removing one edge will result in $k+1$ components and $m_{0}-1$ edges. Therefore, $n - (k + 1) \le m_{0} - 1$, and by organizing, we obtain $n - k \le m_{0}$.

From these two facts, it follows by mathematical induction that $n-k \le m$ generally holds.

---

Part 2. $m \le (n-k)(n-k+1)/2$

Suppose all components of $G$ are complete graphs. Then, there will be two complete graphs $K_{i}$, $K_{j}$ with $1 \le j \le i \le n$. Changing these two graphs to $K_{i+1}$, and $K_{j-1}$ respectively, the total number of vertices remains unchanged, but the total number of edges changes as follows: $$ \left[ (i+1)i - i(i-1) \right]/2 - \left[ j(j-1) - (j-1)(j-2) \right]/2 = i - j + 1 $$ This is positive; hence, for $m$ to be maximized, $G$ must have one complete graph with $(n-k+1)$ vertices and $k-1$ isolated vertices. Therefore, the number of edges of $G$ will be $(n-k)(n-(k-1))/2$, and we obtain the desired result.

■