Notes on complete graphs, bipartite graphs, cycle graphs, and adjacency matrices
KN: Number of edges in a complete graph K
yu
Consider the complete graph on N vertices, denoted K
yEvery vertex is connected to every other vertex; there are no loops or multiple edges.
Degree of every vertex in K
y is N−1, since each vertex connects to all the other N−1 vertices.Total degree sum: \sum{v\in V(KN)} \deg(v) = N\,(N-1)
Each edge contributes 2 to the degree sum (one for each endpoint), so the number of edges |E(K
y))| satisfies 2|E(K_N)| = N(N-1)Therefore, |E(K_N)| = \frac{N(N-1)}{2} = \binom{N}{2}
Ways to prove the edge count
Proof 1: Degree-sum argument
Since every vertex has degree N−1, the sum of degrees is N(N−1).
Each edge is counted twice in the degree sum, hence 2|E| = N(N−1).
Thus |E| = N(N−1)/2.
Proof 2: Induction on N
Base case: N = 1. K
eq has 0 edges, which matches N(N−1)/2 = 0.Inductive hypothesis: For N = k, |E(K_k)| = k(k−1)/2.
Inductive step: Consider K{k+1}. The first k vertices form Kk with k(k−1)/2 edges. The (k+1)th vertex connects to each of the previous k vertices, adding k new edges. Total edges:
|E(K{k+1})| = |E(Kk)| + k = \frac{k(k-1)}{2} + k = \frac{k(k+1)}{2}.This matches the formula with N = k+1, so by induction the statement holds for all N ≥ 1.
Proof 3: Combinatorial argument
An edge in K_N is simply a 2-element subset of the vertex set.
The number of 2-element subsets of an N-element set is \binom{N}{2} = \frac{N(N-1)}{2}.
Since each 2-element subset corresponds to exactly one edge, |E(K_N)| = \binom{N}{2} = N(N-1)/2.
General formula and notation
Number of ways to choose k vertices from N: \binom{N}{k} = \frac{N!}{k!(N-k)!}.
In the context of KN, edges correspond to k = 2: |E(K_N)| = \binom{N}{2} = \frac{N!}{2!(N-2)!} = \frac{N(N-1)}{2}.
Important note: when counting edges by listing vertex-pairs, each edge is counted twice if you count ordered pairs; hence the division by 2 in the final count.
Summary formula
For the complete graph on N vertices, the number of edges is
|E(K_N)| = \binom{N}{2} = \frac{N(N-1)}{2}.
Connections and implications
This result links graph structure to basic combinatorics (binomial coefficients).
It underpins network design considerations: density, average degree, and scalability.
In real-world networks, complete graphs represent idealized maximum connectivity, often used as a benchmark.
Related concepts
Degree sequence: all degrees are N−1 for K_N.
Edge density: for KN, density is 1 (complete connectivity).
If loops or multiple edges were allowed, the simple graph assumption would need adjustment.
Practical applications
Modeling fully connected networks (e.g., fully connected social groups, complete communication networks) as a reference for maximum connectivity.
Ethical/philosophical/practical implications
Understanding limits of connectivity helps in resource planning (e.g., wiring, channels) and informs discussions on network transparency and centralization in dense networks.
Other graph families and concepts
Cycle graph C
yDefinition: A cycle graph on N vertices, denoted C_N, consists of N vertices arranged in a single cycle where each vertex has degree 2.
Edge count: |E(C_N)| = N\, (N \ge 3).
Properties: each vertex connected to two neighbors; graph is 2-regular and connected for N ≥ 3.
Bipartite graphs
Structure: Vertex set V is partitioned into two disjoint sets V1 and V2 with V = V1 \cup V2 and V1 \cap V2 = ∅.
Edge form: every edge connects a vertex from V1 to a vertex from V2; no edges inside V1 or inside V2.
Complete bipartite graph K_{m,n}
Parameters: m = |V1|, n = |V2|, with |V| = m + n.
Edge set: all possible edges between V1 and V2; hence |E(K_{m,n})| = m n.
Example: K_{2,5} has 2×5 = 10 edges and 7 vertices.
Notes
A bipartite graph with partitions V1 and V2 has no odd cycles.
For any bipartite graph, the vertex set can be colored with two colors so that no adjacent vertices share a color.
Adjacency matrix
Definition: For a simple graph with N vertices, the adjacency matrix A is an N×N matrix where
A_{ij} = 1 if there is an edge between vertices i and j,
A_{ij} = 0 otherwise.
Properties
A is symmetric for undirected graphs: A = A^T.
Diagonal entries reflect loops; for a simple graph with no loops, A_{ii} = 0 for all i.
Example interpretation
The matrix encodes the entire edge structure of the graph, enabling algebraic methods for analyzing connectivity, paths, and spectral properties.
Practical notes on matrices in graphs
Adjacency matrix is one of several matrix representations (also Laplacian, incidence, etc.) used in graph algorithms.
For large graphs, adjacency lists are often more space-efficient than dense matrices, but matrices enable efficient linear-algebra-based techniques.
Connections to the transcript content
The transcript outlines multiple proofs of the edge count in a complete graph: degree-sum argument, induction on N, and a combinatorial argument via 2-element vertex sets.
It introduces basic graph types (cycle, bipartite, complete bipartite) and their properties, along with the concept of an adjacency matrix as a way to encode graph information.
Quick reference formulas (LaTeX)
Edge count in KN: |E(K_N)| = \binom{N}{2} = \frac{N(N-1)}{2}.
Degree of each vertex in KN: \deg(v) = N-1.
Sum of degrees: \sum{v\in V(KN)} \deg(v) = N(N-1).
Edge count via induction: |E(K{k+1})| = |E(Kk)| + k.
General binomial coefficient: \binom{N}{k} = \frac{N!}{k!(N-k)!}.
For complete bipartite graph: |V| = m+n, \quad |E(K_{m,n})| = mn.
Cycle graph edges: |E(C_N)| = N \quad (N \ge 3).
Adjacency matrix entries: A_{ij} = \begin{cases} 1, & \text{if edge } {i,j} \text{ exists}, \ 0, & \text{otherwise}. \end{cases}
Summary takeaway
KN has exactly (\frac{N(N-1)}{2}) edges, which can be derived by multiple independent methods.
Many graph classes (cycle, bipartite, complete bipartite) have simple, well-defined edge counts and structural properties that distinguish them from KN.
The adjacency matrix provides a compact, algebraic representation of a graph's connectivity, enabling analysis via linear algebra.