Connectedness – Detailed Study Notes

2.0 Introduction

• Graphs are used to model communication/transport networks, molecular structures, etc.
• Key practical question: which destinations (vertices) are mutually reachable?
• When every pair of vertices is mutually reachable via edges, the graph is called connected.
• Unit roadmap:
• Sec 2.2 – definitions of connected graphs; proof that every graph can be decomposed into connected subgraphs (components).
• Sec 2.3 – bipartite graphs, important in electronics & neural-network modelling.
• Sec 2.4 – trees, whose properties are useful in chemistry (e.g., butane / isobutane) and many real-life structures.

2.1 Objectives

• Distinguish walks, paths, circuits, cycles.
• Identify components of graphs.
• Define / recognise bipartite graphs & trees.

2.2 Connected Graphs

Connected graphs are introduced through “ways of going from one vertex to another”.

2.2.1 Walks, Paths, Circuits & Cycles

• Graph of Fig 1 used for intuition (vertices x<em>1…x</em>12x<em>1 \dots x</em>{12}).
• Example non-minimal walk x<em>1,x</em>2,…,x12{x<em>1,x</em>2,\dots,x_{12}} shows repetition & detours.

Formal Definitions

• Walk W=v<em>0,e</em>1,v<em>1,…,e</em>k,v<em>kW = {v<em>0,e</em>1,v<em>1,\dots ,e</em>k,v<em>k} with each e</em>ie</em>i joining v<em>i−1v<em>{i-1} & v</em>iv</em>i.
• Initial vertex v<em>0v<em>0, end vertex v</em>kv</em>k.
• Length λ(W)=k\lambda(W)=k (number of edges – can exceed |E| because of repetition).
• Path – a walk whose vertices (hence edges) are all distinct.
• Closed / open walk – closed if initial = end vertex, otherwise open.
• Cycle – closed walk with no repeated edge and the only repeated vertex being the first (= last).
• Edges-distinct ⇒ vertices-distinct? Not necessarily (exercise E2).

Worked Examples

• Fig 2 (5 vertices, 7 edges):
• Length 8 walk from x<em>1x<em>1 to x</em>5x</em>5: x<em>1,x</em>2,x<em>3,x</em>4,x<em>2,x</em>5,x<em>3,x</em>4,x<em>5{x<em>1,x</em>2,x<em>3,x</em>4,x<em>2,x</em>5,x<em>3,x</em>4,x<em>5}. • Length 4 walk: x</em>1,x<em>2,x</em>4,x<em>3,x</em>5{x</em>1,x<em>2,x</em>4,x<em>3,x</em>5}.
• Example of closed non-cycle, non-path etc. in Fig 4.

Fundamental Theorem on Existence of Paths

Theorem 1: Any u-v walk contains a u-v path.
• Proof uses induction on walk length.
• Important because it allows reasoning about connectivity via paths instead of arbitrary walks.

Exercises (brief)

E1–E5 reinforce definition work.

2.2.2 Components

• Connected graph: every pair of vertices joined by a walk (equivalently by a path via Th 1).
• Disconnected graph: not connected.
• Component: maximal connected subgraph. Denote number by c(G)c(G).
• Null graph on n vertices has c(G)=nc(G)=n.
• Theorem 2: Every graph can be partitioned into its components.
• Theorem 3 (edge bounds): For graph with nn vertices & kk components,
n−k≤m≤(n−k)(n−k+1)2n-k \le m \le \frac{(n-k)(n-k+1)}{2}.
• Corollary 1 (connected case k=1k=1): n−1≤m≤n(n−1)2n-1 \le m \le \frac{n(n-1)}{2}.

2.2.3 Connectivity Measures

Bridges (Cut Edges)

• Edge whose removal increases c(G)c(G).
• Notation: G−eG-e for graph with edge e removed.
• Edge is a bridge ⇔ it lies in no cycle.

Edge-Connectivity λ(G)\lambda(G)

• Minimum number of edges whose removal disconnects G.
• If G has a bridge, λ(G)=1\lambda(G)=1.
• Example (Fig 14) – graph with λ(G)=2\lambda(G)=2 (sets {xz,zy}, {xv,vu}, {uw,wy} each suffice).
• Real-world meaning: number of simultaneous link failures tolerable in a network.

Cutsets (Edge-cutsets)

• Set S of edges whose total removal disconnects G, but no proper subset of S does.
• Smallest cutset size = λ(G)\lambda(G) (edge-connectivity).

Vertex-Connectivity κ(G)\kappa(G) and Vertex-Cutsets

• Cut-vertex: vertex whose deletion disconnects G.
• κ(G)\kappa(G) = minimum number of vertices whose removal disconnects G.
• Exercises E17–E18 develop formal definitions & computation.

2.3 Bipartite Graphs

• Motivating assignment problem: 4 people x<em>1…x</em>4x<em>1\dots x</em>4 vs. 5 jobs y<em>1…y</em>5y<em>1\dots y</em>5 (qualifications given).
• Model with graph G(X,Y)G(X,Y): edge x<em>iy</em>jx<em>i y</em>j iff x<em>ix<em>i qualified for y</em>jy</em>j.
• Bipartite graph: vertex set can be partitioned into two non-empty disjoint sets X,Y such that every edge joins an X-vertex to a Y-vertex (equivalently, 2-colourable).
• Complete bipartite K<em>r,sK<em>{r,s} has every X vertex adjacent to every Y vertex. Examples: K</em>1,nK</em>{1,n} (star), K<em>2,3K<em>{2,3}, K</em>3,3K</em>{3,3} etc.
• Uniqueness of bipartition: connected bipartite graphs have a unique bipartition (Theorem 4).
• Characterisation (Theorem 5): Graph is bipartite ⇔ contains no odd cycle.
• Applications: electronic circuits, neural networks (Fig 18), hypercubes, star topologies.

Matchings & Hall’s Condition

• Matching: set of edges with pairwise-disjoint endpoints.
• Complete matching of X into Y: every vertex of X is incident to exactly one edge of the matching.
• Hall’s Theorem (Theorem 6): A complete matching of X into Y exists ⇔ for every subset A⊆XA \subseteq X, ∣A∣≤∣R(A)∣|A| \le |R(A)| where R(A)R(A) = set of neighbours of A in Y.
• Worked table (Example 6) verifies condition for the 4-person 5-job problem ⟹ feasible assignment.

2.4 Trees & Forests

• Historical origin: Kirchhoff (electrical circuits, 1840s), Cayley (enumerating chemical molecules, 1870s).
• Tree: connected graph without cycles.
• Forest: graph whose every component is a tree (acyclic, may be disconnected).

Equivalent Characterisations (Theorem 7)

For graph G on nn vertices, the following are equivalent:

  1. G is a tree.

  2. G has no cycles and exactly n−1n-1 edges.

  3. G is connected and has n−1n-1 edges.

  4. G is connected and every edge is a bridge.

  5. Every pair of vertices is connected by exactly one path.
    • Inductive proof sketched (implication chain (i)→(ii)→…→(v)→(i)).

Spanning Trees

• Any connected graph can have edges removed (one per cycle) until acyclic; resulting connected subgraph with all vertices is a spanning tree.
• Spanning tree is not necessarily unique (Fig 26 with two different spanning trees T₁, T₂).
• Importance: minimum road set to keep connectivity; data-network multicast routing (loop-free).
• Theorem 8: Graph is connected ⇔ it possesses a spanning tree.

Miscellaneous Properties & Examples

• Star K<em>1,nK<em>{1,n} is a tree for any n≥1n\ge1. • K</em>m,nK</em>{m,n} is a tree iff m=1 or n=1m=1\text{ or }n=1 (i.e.
star form).
• Trees are always bipartite (no cycles ⇒ no odd cycle).

2.5 Unit Summary (Key Take-aways)

• Precise definitions of walks, paths, cycles; every walk contains a path between same endpoints.
• Connectedness, decomposition into components; edge/vertex removals’ effect on c(G)c(G).
• Edge bounds n−k≤m≤(n−k)(n−k+1)2n-k \le m \le \frac{(n-k)(n-k+1)}{2} for n-vertex, k-component graph.
• Bipartite graphs characterised by absence of odd cycles; complete matchings via Hall’s condition.
• Trees: many equivalent views; every connected graph contains a spanning tree; trees are inherently bipartite.
• Connectivity parameters λ(G)\lambda(G) (edges) & κ(G)\kappa(G) (vertices) quantify robustness of networks.

2.6 Selected Exercises & Insights (quick recall)

• Find walks of prescribed length (E1), show example where distinct edges≠distinct vertices (E2).
• Induction proof that minimum degree δ(G)≥k\delta(G) \ge k guarantees path length kk from any start (E4).
• Edge-connectivity of C<em>nC<em>n is 22, of K</em>nK</em>n is n−1n-1 (E14).
• Hypercube Q3Q_3 & stars are bipartite; complement of bipartite graph need not be bipartite (E21).
• Trees have n−1n-1 edges; multiple spanning trees exist for same graph; trees are bipartite (E27).