Connectedness

Connected Graph

An undirected graph is connected iff every pair of vertices is connected by a path. Otherwise the graph is disconnected.

For directed graph, all directionality is dropped and connectivity is checked.

A graph is disconnected iff its vertex set can be split into 2 disjoint non-empty sets with no edges between them.

A graph is connected iff every entry of $A + A^2 + \dots + A^{n-1}$ is non-zero.

In a connected graph with $n \ge 2$ vertices, any two vertices are connected by a path of length $k$ where $k \le n - 1$.

Connected Component

A maximal connected subgraph. Every pair of vertices inside are connected. No connection to outside vertices. Each component is an isolated piece of a graph.

A connected graph has exactly 1 connected component which is itself. A disconnected graph has more than 2 components.

Distance

Length of the shortest path between two vertices. Denoted as $\text{dist}(u, v)$. if no path exists, $dist(u, v) = \infty$. If a path exists between $u,v$, then $\text{dist}(u,v) \le n - 1$.

Properties:

• Non-negativity
  $\text{dist}(u, v) \ge 0$.
• Identity
  $\text{dist}(u, v) = 0 ⇔ u = v$.
• Symmetry
  $\text{dist}(u, v) = \text{dist}(v, u)$.
• Triangle inequality
  $\text{dist}(u, w) \le \text{dist}(u, v) + \text{dist}(v, w)$.

For $K_n$, $\text{dist}(u,v)=1$ for any $u,v$ pair.

Diameter

Maximum distance between any two vertices. Denoted as $\text{diam}(G)$.

Measures the largest shortest path in the graph.

For $K_n$, $\text{diam}(u,v)=1$.