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 ).
• Example non-minimal walk shows repetition & detours.
Formal Definitions
• Walk with each joining & .
• Initial vertex , end vertex .
• Length (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 to : . • Length 4 walk: .
• 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 .
• Null graph on n vertices has .
• Theorem 2: Every graph can be partitioned into its components.
• Theorem 3 (edge bounds): For graph with vertices & components,
.
• Corollary 1 (connected case ): .
2.2.3 Connectivity Measures
Bridges (Cut Edges)
• Edge whose removal increases .
• Notation: for graph with edge e removed.
• Edge is a bridge ⇔ it lies in no cycle.
Edge-Connectivity
• Minimum number of edges whose removal disconnects G.
• If G has a bridge, .
• Example (Fig 14) – graph with (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 = (edge-connectivity).
Vertex-Connectivity and Vertex-Cutsets
• Cut-vertex: vertex whose deletion disconnects 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 vs. 5 jobs (qualifications given).
• Model with graph : edge iff qualified for .
• 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 has every X vertex adjacent to every Y vertex. Examples: (star), , 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 , where = 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 vertices, the following are equivalent:
G is a tree.
G has no cycles and exactly edges.
G is connected and has edges.
G is connected and every edge is a bridge.
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 is a tree for any . • is a tree iff (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 .
• Edge bounds 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 (edges) & (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 guarantees path length from any start (E4).
• Edge-connectivity of is , of is (E14).
• Hypercube & stars are bipartite; complement of bipartite graph need not be bipartite (E21).
• Trees have edges; multiple spanning trees exist for same graph; trees are bipartite (E27).