Graph Connectivity, Network Reliability, and Discrete Mathematics Test Review

Communication Networks and Graph Connectivity Fundamentals

  • Communication networks are mathematically modeled as connected graphs where vertices represent nodes or servers and edges represent physical or wireless communication links.
  • In a fully connected network model (e.g., spanning from Boston across regional hubs to Denver, San Francisco, and Los Angeles), all nodes can route traffic to one another.
  • Single points of failure pose critical vulnerabilities to network reliability:
    • If a critical link fails, the graph splits into multiple disconnected subnetworks that cannot exchange data.
    • If an essential routing node fails (such as a server in Denver going offline), peripheral nodes (such as San Francisco and Los Angeles) become entirely isolated from the rest of the network.
  • Fundamental relationship between vertices, edges, and connected components:
    • Let a graph have nn vertices and kk edges.
    • A graph consisting purely of nn vertices and 00 edges contains exactly nn isolated connected components.
    • Adding a single edge between two previously disconnected components reduces the total number of connected components by exactly 11.
    • If an edge is introduced between two vertices already in the same component, the number of connected components remains unchanged.
    • Consequently, the minimum number of connected components in a graph with nn vertices and kk edges is given by the lower bound n−kn - k.
    • Example with graph HH: A graph containing n=8n = 8 vertices and k=6k = 6 edges can form 33 connected components.
    • Example with a 7-vertex graph: If n=7n = 7 and only k=4k = 4 edges are present, the graph cannot be connected. The minimum possible number of connected components is 7−4=37 - 4 = 3.

Vertex Cuts and Vertex Connectivity

  • A cut vertex (or articulation point) of a graph GG is a single vertex vv whose removal—along with all incident edges—strictly increases the number of connected components of GG, thereby rendering a previously connected graph disconnected.
  • A vertex cut (or separating set) is a set of vertices S≠ØS \ne \text{\O} such that the induced subgraph on V(G)∖SV(G) \setminus S is disconnected or consists of a single isolated vertex.
  • The vertex connectivity of a graph GG, denoted by κ(G)\kappa(G), is the minimum cardinality (size) of a vertex cut in GG:
    • κ(G)=min⁡{∣S∣:S⊆V(G) is a vertex cut}\kappa(G) = \min \{ |S| : S \subseteq V(G) \text{ is a vertex cut} \}
    • A higher vertex connectivity indicates greater structural resilience against node failure.
  • Vertex connectivity across standard graph topologies:
    • Path Graph PnP_n (for n≥3n \ge 3, e.g., P5P_5):
    • Removing any internal vertex partitions the path into two disconnected paths.
    • Vertex connectivity: κ(Pn)=1\kappa(P_n) = 1.
    • Cycle Graph CnC_n (for n≥3n \ge 3, e.g., C6C_6):
    • Removing one vertex leaves a connected path graph Pn−1P_{n-1}.
    • Removing any two non-adjacent (or distinct) vertices separates the cycle into disconnected path segments.
    • Vertex connectivity: κ(Cn)=2\kappa(C_n) = 2.
    • Wheel Graph WnW_n (for n≥4n \ge 4, e.g., W7W_7):
    • A wheel graph consists of an outer cycle of n−1n - 1 vertices connected to a central hub vertex.
    • Removing the central hub leaves the cycle intact.
    • Disconnecting the wheel requires removing the hub plus at least two vertices from the cycle rim.
    • Vertex connectivity: κ(Wn)=3\kappa(W_n) = 3, invariant with respect to the total number of vertices nn.
    • Complete Bipartite Graph Km,nK_{m,n} (e.g., K4,5K_{4,5}, K100,108K_{100,108}):
    • A graph partitioned into two disjoint independent sets of size mm and nn, with every vertex in the first set adjacent to every vertex in the second set.
    • Disconnecting the graph entirely requires removing all vertices of the smaller partition set, which leaves the remaining partition set as completely isolated vertices.
    • Vertex connectivity: κ(Km,n)=min⁡(m,n)\kappa(K_{m,n}) = \min(m, n).
    • For K4,5K_{4,5}, removing the 44 vertices of the first partition disconnects the graph; hence, κ(K4,5)=4\kappa(K_{4,5}) = 4.
    • For K100,108K_{100,108}, the minimum number of vertices needed to disconnect the graph is min⁡(100,108)=100\min(100, 108) = 100.
  • Network Resilience versus Construction Cost Trade-off:
    • Complete bipartite networks provide extreme resilience against vertex loss (e.g., surviving the failure of up to m−1m - 1 nodes).
    • Achieving this resilience requires constructing a large number of edges (m×nm \times n links).
    • This embodies the principle of physical leverage (the law of the lever: lifting a heavier load requires moving through a proportionally longer distance). In graph theory, higher connectivity requires an increased density of edges.

Edge Cuts and Edge Connectivity

  • A cut edge (or bridge) is an edge whose removal strictly increases the number of connected components of the graph.
    • Crucial operational distinction between vertex removal and edge removal: removing a vertex automatically deletes the vertex and all its incident edges; removing an edge deletes only the connection, leaving the endpoint vertices intact in the graph.
  • An edge cut is a set of edges E′⊆E(G)E' \subseteq E(G) whose deletion produces a disconnected subgraph G−E′G - E'.
  • Edge connectivity, denoted by λ(G)\lambda(G), is the minimum number of edges whose removal disconnects GG:
    • If a graph GG is already disconnected, its edge connectivity is formally defined as λ(G)=0\lambda(G) = 0.
  • Fundamental connectivity inequality (Whitney's Theorem):
    • For any graph GG:     κ(G)≤λ(G)≤δ(G)\kappa(G) \le \lambda(G) \le \delta(G)
    • Here, δ(G)=min⁡v∈V(G)deg(v)\delta(G) = \min_{v \in V(G)} \text{deg}(v) denotes the minimum degree among all vertices in GG.
  • Designing Graphs with Divergent Connectivities:
    • For many symmetric graphs, κ(G)=λ(G)\kappa(G) = \lambda(G).
    • However, a graph can be constructed such that κ(G)=1\kappa(G) = 1 while λ(G)=2\lambda(G) = 2.
    • Construction: Take two independent cycles (each having internal edge connectivity of 22) and join them at a single shared cut vertex (a bowtie / figure-eight topology). Removing that single vertex splits the graph into two components (κ(G)=1\kappa(G) = 1), but disconnecting the graph purely by removing edges requires cutting at least two edges of either cycle (λ(G)=2\lambda(G) = 2).
  • Exception for Complete Graphs KnK_n (n≥3n \ge 3):
    • In a complete graph, every pair of distinct vertices is connected by an edge.
    • Removing any vertex leaves Kn−1K_{n-1}, which remains fully connected.
    • Consequently, complete graphs have no vertex cut in the classical sense of producing a disconnected graph; by standard convention, its connectivity is defined as κ(Kn)=n−1\kappa(K_n) = n - 1.
  • Practical network application:
    • Highway networks: Vertices represent intersections and edges represent highway road segments.
    • Road closures (edge failures) and intersection blockages (vertex failures) dictate traffic re-routing and vulnerability to complete regional isolation.

Case Studies: Analysis of Specific Graph Configurations

  • Graph G1G_1:
    • Cut vertices: Vertex CC.
    • Cut edges: Edge CECE.
    • Vertex connectivity: κ(G1)=1\kappa(G_1) = 1.
    • Minimum edge disconnection: While CECE is a cut edge (disconnecting EE with 11 edge removal), isolating other components requires removing multiple edges, such as the pair of edges {AB,AC}\{AB, AC\}.
  • Graph G3G_3:
    • Vertex analysis: Contains no single cut vertex (κ(G3)>1\kappa(G_3) > 1); there is always an alternate path around any single deleted vertex.
    • Vertex cut: The set of two vertices {D,G}\{D, G\} forms a valid vertex cut that separates vertex AA from the remaining components.
    • Vertex connectivity: κ(G3)=2\kappa(G_3) = 2.
  • Graph G4G_4:
    • Cut vertex analysis: Possesses no single cut vertex.
    • Vertex cut: The set {C,F}\{C, F\} acts as a vertex cut, partitioning the graph into two disconnected components upon removal.
    • Vertex connectivity: κ(G4)=2\kappa(G_4) = 2.
    • Satisfies the general inequality: κ(G)≤λ(G)\kappa(G) \le \lambda(G).
  • Graph G5G_5:
    • Advanced configuration designated for independent connectivity analysis.

Test 1 Review: Common Errors and Algorithmic Solutions

  • Pedagogical perspective on academic assessment:
    • Evaluation performance serves as diagnostic feedback: "FAIL" is defined as "First Attempt In Learning."
    • Errors should be analyzed systematically via targeted reflection worksheets.
  • Number Theory: Divisibility Properties with Zero:
    • Zero cannot serve as a divisor: 0∤50 \nmid 5 (50\frac{5}{0} is mathematically undefined).
  • Any non-zero integer divides zero: a∣0a \mid 0 for all a≠0a \ne 0, because there exists an integer c=0c = 0 such that 0=a×00 = a \times 0.
  • Mental Modular Arithmetic Strategies:
    • Calculations should be performed using modular reduction at each intermediate step rather than computing massive products by hand ("work smarter, not harder").
    • When calculating modulo 1010, every intermediate value is replaced by its remainder upon division by 1010 (e.g., working with remainders 77, 33, 11, and 22 directly).
  • Method of Repeated Squaring:
    • Used to compute large modular powers ab(modm)a^b \pmod{m} efficiently.
    • Common error: incorrectly performing arithmetic operations rather than systematically calculating powers of two (a1,a2,a4,a8,…a^1, a^2, a^4, a^8, \dots) modulo mm and multiplying the corresponding components.
  • Euclidean Algorithm, GCD, and LCM:
    • The Euclidean algorithm must be applied systematically via repeated division:     gcd⁡(a,b)=gcd⁡(b,a(modb))\gcd(a, b) = \gcd(b, a \pmod{b})
    • Least Common Multiple (lcm\text{lcm}) is derived directly from the greatest common divisor:     lcm(a,b)=∣a×b∣gcd⁡(a,b)\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}
    • Students frequently lose credit by guessing or using prime factorizations instead of executing the required Euclidean division steps.
  • Multiplicative Inverses Modulo mm:
    • An integer aa has a multiplicative inverse modulo mm if and only if aa and mm are coprime:     gcd⁡(a,m)=1\gcd(a, m) = 1
    • Example with modulo 3030:
    • Any number sharing a common factor with 3030 (factors 2,3,52, 3, 5) lacks an inverse.
    • Only values where gcd⁡(a,30)=1\gcd(a, 30) = 1 have valid modular inverses.
    • Example: Finding the multiplicative inverse of 6(mod29)6 \pmod{29}:
    • Because 2929 is prime and gcd⁡(6,29)=1\gcd(6, 29) = 1, the inverse exists and is unique modulo 2929.
  • Solving Linear Congruences for Complete Solution Sets:
    • To solve an equation such as finding solutions modulo 3838:
    • Given an inverse multiplication step yielding 44(mod38)≡644 \pmod{38} \equiv 6, finding x=6x = 6 is only a single particular solution.
    • When asked for all integer solutions, the result cannot be stated as merely a single number.
    • Using the modular arithmetic clock model of size 3838, the complete solution set in Z\mathbb{Z} is:       x=6+38kfor all k∈Zx = 6 + 38k \quad \text{for all } k \in \mathbb{Z}
  • Binary Relations and Structural Properties:
    • Clear relation notation requires listing explicit ordered pairs (e.g., S1={(1,1),(1,2)}S_1 = \{(1, 1), (1, 2)\}).
    • Transitivity check: If (a,b)∈R(a, b) \in R and (b,c)∈R(b, c) \in R, then (a,c)(a, c) must belong to RR.
    • Analysis of Relation R1R_1:
    • Reflexivity: R1R_1 is reflexive because (x,x)∈R1(x, x) \in R_1 for every element in the domain.
    • Symmetry failure: R1R_1 is not symmetric because (3,0)∈R1(3, 0) \in R_1, but (0,3)∉R1(0, 3) \notin R_1.
  • Antisymmetry failure: R1R_1 is not antisymmetric because both (0,1)∈R1(0, 1) \in R_1 and (1,0)∈R1(1, 0) \in R_1 exist within the relation while 0≠10 \ne 1.

Questions & Practical Worksheet Exercises

  • Problem 1: Disconnecting paths and cycles
    • Prompt: What is the vertex connectivity of a path graph P5P_5 versus a cycle graph C6C_6?
    • Answer: For P5P_5, removing one interior vertex disconnects the graph (κ(P5)=1\kappa(P_5) = 1). For C6C_6, removing one vertex leaves a path, but removing two vertices breaks the cycle into disconnected pieces (κ(C6)=2\kappa(C_6) = 2).
  • Problem 2: Connectivity of complete bipartite networks
    • Prompt: For K4,5K_{4,5}, how many vertices must be disconnected to break the graph?
    • Answer: Disconnecting 44 vertices from the smaller partition disconnects the graph completely. Disconnecting the 55 vertices also works, but the minimum cut size is 44. Hence, κ(K4,5)=4\kappa(K_{4,5}) = 4.
  • Problem 3: Generalization of complete bipartite graphs
    • Prompt: How should the vertex connectivity of Km,nK_{m,n} be expressed mathematically for arbitrary partitions mm and nn (e.g., K100,108K_{100,108})?
    • Answer: It must be expressed as min⁡(m,n)\min(m, n). For K100,108K_{100, 108}, the vertex connectivity is exactly 100100.
  • Problem 4: Construction challenge for divergent connectivity
    • Prompt: Can a graph be constructed where vertex connectivity is 11 and edge connectivity is 22?
    • Answer: Yes; two cycles joined at a single vertex (sharing an articulation point) has κ(G)=1\kappa(G) = 1 because cutting that one vertex separates the two cycles. Its edge connectivity is λ(G)=2\lambda(G) = 2 because cutting any single edge within either cycle leaves the cycle connected as a path through the shared vertex.
  • Problem 5: Linear congruence complete integer solution
    • Prompt: If x≡6(mod38)x \equiv 6 \pmod{38}, what is the complete set of integer solutions?
    • Answer: The full set of solutions is all integers of the form x=6+38kx = 6 + 38k, where k∈Zk \in \mathbb{Z}.