X_401010 Networks and Graphs
Index
Chapter 2 - Foundations ....................................................................................................................................1
Chapter 3 - Extensions ......................................................................................................................................3
Chapter 4 - Network Traversal ..........................................................................................................................3
Chapter 5 - Trees ...............................................................................................................................................5
Chapter 6 - Network Analysis ...........................................................................................................................6
Chapter 7 - Random Networks..........................................................................................................................7
Chapter 9 - Social Networks .............................................................................................................................8
Chapter 2 - Foundations
➤2.1 Graphs & Degrees
• Graph(G): Consists of V(G) set of vertices and E(G) set of edges.
• Edge: Connects 2 vertices u and v and is denoted by ⟨u, v⟩.
• For any u ∈ V(G) the neighbor set N(u) is the set of all vertices adjacent to u except for u itself.
• A graph is simple if it does not contain multiple edges between the same pair of vertices nor loops.
• The degree δ(v) of a vertex is the number of edges attached to vertex v. Loops are counted twice.
• Handshaking lemma: ∑v ∈ V(G)δ(v) = 2 |E(G)| for all graphs G, meaning for any graph the sum of the
degrees of vertices equals 2 times the number of edges in the graph.
• Degree sequence: A list of the degrees of the vertices in a graph. It is ordered if the numbers are in
non-increasing order. E.g. [1,0,0] & [2,2,2]
• A sequence of numbers is graphic if it is the degree sequence of a simple graph. E.g. [2,2,2]
➤2.2 Two Ways of Graph Representation
• Properties of an adjacency matrix:
- Symmetry i.e. ∀u, v : A[u, v] = A[v, u]
- Whether a graph is simple or not i.e. ∀u, v : A[u, v] ≤ 1 and A[u, u] = 0
- The sum of the numbers on each row should be equal to the degree of that vertex.
• Properties of an incidence matrix:
- The sum of the numbers in each column must be exactly 2.
- The sum of the numbers on each row should be equal to the degree of that vertex.
Fig.1.1 Example graph Fig.1.2 Matrices for the graph (1):Adjacency (2):Incidence
➤2.3 Subgraphs
• H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and for all ⟨u, v⟩ ∈ E(H) there is u, v ∈ V(H).
• G[V*]: Subgraph induced by V* ⊆ V(G) has vertex set V* and edge set {⟨u, v⟩ ∈ E(G) | u, v ∈ V*}.
• G[E*]: Subgraph induced by E* ⊆ E(G) has edge set E* and vertex set {u, v ∈ V(G) | ⟨u, v⟩ ∈ E*}.
➤2.4 Graph Isomorphisms
• Graphs G1 and G2 are isomorphic if there is a one-to-one mapping. φ : V(G1) → V(G2). The graphs
have vertices with the same combinations of edges.
• For 2 graphs to be isomorphic it has to have the same amount of vertices, edges, and the ordered
degree sequence of the graphs have to be the same.
• Further it can be determined by the naïve algorithm or the Babai and Luks algorithm.
➤2.5 The Theorem of Havel-Hakimi
• Let [s, t1, t2, …, ts, d1, …, dn] be an ordered sequence. This sequence is graphic if and only if the
sequence [t1 - 1, t2 - 1, …, ts - 1, d1, …, dn] is graphic too.
• To determine this with the Havel-Hakimi theorem, continuously apply the “only if direction” (erase
the most left vertex) until the base case is reached. Then determine whether the base case is graphic.
• E.g. [4,4,2,2,2] => [3,1,1,1] => [0,0,0]. [0,0,0] is graphic, therefore [4,4,2,2,2] is graphic.
1
, ➤2.7 Paths, Cycles and Connectivity
• A (v0, vk)-walk is a sequence [v0, e1, v1, e2, …, vk - 1, ek, vk] with ei = ⟨vi - 1, vi⟩ for all i = 1,…,k.
• A (u, v)-path is a (u, v)-walk over distinct vertices.
• In a simple graph, a cycle is a (u, v)-path of at least 3 edges over distinct vertices except u = v.
• If a simple graph does not contain any cycles, it is acyclic.
• Two vertices u, v in G are connected if there is a (u, v)-path in G.
• Connectivity indicates that each vertex can be reached by any other vertex in the network.
• A component of a graph G is a connected subgraph that is not strictly contained in another connected
subgraph of G.
➤2.8 Vertex and Edge Cuts
• V* ⊆ V(G) is a vertex cut of G if removing the vertices in V* (and their edges) from G yields a non-
connected graph.
• E* ⊆ E(G) is an edge cut of G if removing the edge in E* from G yields a non-connected graph.
• It is of interest to find the minimum number of vertices or edges to remove for a graph to fall apart. So,
κ(G) is the minimum vertices that need to be removed, and λ(G) is the minimum number of edges.
• κ(G) ≤ λ(G) ≤ minv ∈ V(G){δ(v)}(minimum degree of G)
➤2.8 K-Connectivity and Harary Graphs
• A graph G is k-connected if κ(G) ≥ k vertices. Meaning you can’t disconnect Hk, n by removing less
than k vertices.
• Harary graph(Hk, n): A k-connected simple graph with n vertices and with a minimal number of
edges. There are 3 cases for combinations of k and n.
- k is even: Connect each vertex to its k/2 closest left-hand & right-hand neighbors.
- k is odd, n is even: Construct Hk-1, n and add n/2 edges, joining vertices at n/2 distance(opposites)
- k is odd, n is odd: Construct Hk-1, n and add the (n+1)/2 edges, joining vertices at (n-1)/2 distance
• The vertices in all have degree k, except if k and n are both odd, then vertex (n-1)/2 has degree k + 1.
➤2.9 Menger’s Theorem
• Let P(u, v) be a set of (u, v)-paths in a simple graph:
- Vertex independent: ∀P, Q ∈ P(u, v) : V(P) ∩ V(Q) = {u, v}, different paths that have only u and
v in common.
- Edge independent: ∀P, Q ∈ P(u, v) : E(P) ∩ E(Q) = ∅, different paths don’t share any edges.
• Menger’s Theorem: The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v
equals the maximum size of a vertex-independent set P(u, v). The minimum size of an edge cut
disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u, v).
➤2.10 Bipartite Graphs
• A graph G is bipartite if V(G) = V1 ∪ V2 (G is split in two) such that:
- V1 ∩ V2 = ∅; they don’t have shared vertices
- E(G) ⊆ {⟨u, v⟩ | v1 ∈ V1 and v2 ∈ V2 }; any edge of G must connect a vertex from V1 to one of V2.
• Bipartite graphs are often drawn as ranked embeddings. This will make it more obvious to say
whether a graph is bipartite or not. A ranked embedding is made as follows:
- Choose a vertex and put all the vertices where they’re connected to through an edge in a
horizontal row above. Do the same with those vertices until all vertices are in a row.
- If all the vertices on the same row do not have an edge connected them, the graph is bipartite.
- The number of rows is the number of possible disjoint subsets.
➤2.11 Planar Graphs & Euler’s Formula
• A simple and connected graph is planar if there exists a drawing in the 2D plane such that no two
edges cross.
• In any planar graph of n ≥ 1 vertices, m ≥ 0 edges and r ≥ 1 regions (regions closed off because of
edges and vertices, including the exterior region), then n − m + r = 2. This is the Euler’s formula.
• For any planar graph G with n ≥ 3 vertices and m edges: m ≤ 3n − 6.
• Every planar graph G has at least one vertex v with δ(v) ≤ 5.
2
Index
Chapter 2 - Foundations ....................................................................................................................................1
Chapter 3 - Extensions ......................................................................................................................................3
Chapter 4 - Network Traversal ..........................................................................................................................3
Chapter 5 - Trees ...............................................................................................................................................5
Chapter 6 - Network Analysis ...........................................................................................................................6
Chapter 7 - Random Networks..........................................................................................................................7
Chapter 9 - Social Networks .............................................................................................................................8
Chapter 2 - Foundations
➤2.1 Graphs & Degrees
• Graph(G): Consists of V(G) set of vertices and E(G) set of edges.
• Edge: Connects 2 vertices u and v and is denoted by ⟨u, v⟩.
• For any u ∈ V(G) the neighbor set N(u) is the set of all vertices adjacent to u except for u itself.
• A graph is simple if it does not contain multiple edges between the same pair of vertices nor loops.
• The degree δ(v) of a vertex is the number of edges attached to vertex v. Loops are counted twice.
• Handshaking lemma: ∑v ∈ V(G)δ(v) = 2 |E(G)| for all graphs G, meaning for any graph the sum of the
degrees of vertices equals 2 times the number of edges in the graph.
• Degree sequence: A list of the degrees of the vertices in a graph. It is ordered if the numbers are in
non-increasing order. E.g. [1,0,0] & [2,2,2]
• A sequence of numbers is graphic if it is the degree sequence of a simple graph. E.g. [2,2,2]
➤2.2 Two Ways of Graph Representation
• Properties of an adjacency matrix:
- Symmetry i.e. ∀u, v : A[u, v] = A[v, u]
- Whether a graph is simple or not i.e. ∀u, v : A[u, v] ≤ 1 and A[u, u] = 0
- The sum of the numbers on each row should be equal to the degree of that vertex.
• Properties of an incidence matrix:
- The sum of the numbers in each column must be exactly 2.
- The sum of the numbers on each row should be equal to the degree of that vertex.
Fig.1.1 Example graph Fig.1.2 Matrices for the graph (1):Adjacency (2):Incidence
➤2.3 Subgraphs
• H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and for all ⟨u, v⟩ ∈ E(H) there is u, v ∈ V(H).
• G[V*]: Subgraph induced by V* ⊆ V(G) has vertex set V* and edge set {⟨u, v⟩ ∈ E(G) | u, v ∈ V*}.
• G[E*]: Subgraph induced by E* ⊆ E(G) has edge set E* and vertex set {u, v ∈ V(G) | ⟨u, v⟩ ∈ E*}.
➤2.4 Graph Isomorphisms
• Graphs G1 and G2 are isomorphic if there is a one-to-one mapping. φ : V(G1) → V(G2). The graphs
have vertices with the same combinations of edges.
• For 2 graphs to be isomorphic it has to have the same amount of vertices, edges, and the ordered
degree sequence of the graphs have to be the same.
• Further it can be determined by the naïve algorithm or the Babai and Luks algorithm.
➤2.5 The Theorem of Havel-Hakimi
• Let [s, t1, t2, …, ts, d1, …, dn] be an ordered sequence. This sequence is graphic if and only if the
sequence [t1 - 1, t2 - 1, …, ts - 1, d1, …, dn] is graphic too.
• To determine this with the Havel-Hakimi theorem, continuously apply the “only if direction” (erase
the most left vertex) until the base case is reached. Then determine whether the base case is graphic.
• E.g. [4,4,2,2,2] => [3,1,1,1] => [0,0,0]. [0,0,0] is graphic, therefore [4,4,2,2,2] is graphic.
1
, ➤2.7 Paths, Cycles and Connectivity
• A (v0, vk)-walk is a sequence [v0, e1, v1, e2, …, vk - 1, ek, vk] with ei = ⟨vi - 1, vi⟩ for all i = 1,…,k.
• A (u, v)-path is a (u, v)-walk over distinct vertices.
• In a simple graph, a cycle is a (u, v)-path of at least 3 edges over distinct vertices except u = v.
• If a simple graph does not contain any cycles, it is acyclic.
• Two vertices u, v in G are connected if there is a (u, v)-path in G.
• Connectivity indicates that each vertex can be reached by any other vertex in the network.
• A component of a graph G is a connected subgraph that is not strictly contained in another connected
subgraph of G.
➤2.8 Vertex and Edge Cuts
• V* ⊆ V(G) is a vertex cut of G if removing the vertices in V* (and their edges) from G yields a non-
connected graph.
• E* ⊆ E(G) is an edge cut of G if removing the edge in E* from G yields a non-connected graph.
• It is of interest to find the minimum number of vertices or edges to remove for a graph to fall apart. So,
κ(G) is the minimum vertices that need to be removed, and λ(G) is the minimum number of edges.
• κ(G) ≤ λ(G) ≤ minv ∈ V(G){δ(v)}(minimum degree of G)
➤2.8 K-Connectivity and Harary Graphs
• A graph G is k-connected if κ(G) ≥ k vertices. Meaning you can’t disconnect Hk, n by removing less
than k vertices.
• Harary graph(Hk, n): A k-connected simple graph with n vertices and with a minimal number of
edges. There are 3 cases for combinations of k and n.
- k is even: Connect each vertex to its k/2 closest left-hand & right-hand neighbors.
- k is odd, n is even: Construct Hk-1, n and add n/2 edges, joining vertices at n/2 distance(opposites)
- k is odd, n is odd: Construct Hk-1, n and add the (n+1)/2 edges, joining vertices at (n-1)/2 distance
• The vertices in all have degree k, except if k and n are both odd, then vertex (n-1)/2 has degree k + 1.
➤2.9 Menger’s Theorem
• Let P(u, v) be a set of (u, v)-paths in a simple graph:
- Vertex independent: ∀P, Q ∈ P(u, v) : V(P) ∩ V(Q) = {u, v}, different paths that have only u and
v in common.
- Edge independent: ∀P, Q ∈ P(u, v) : E(P) ∩ E(Q) = ∅, different paths don’t share any edges.
• Menger’s Theorem: The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v
equals the maximum size of a vertex-independent set P(u, v). The minimum size of an edge cut
disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u, v).
➤2.10 Bipartite Graphs
• A graph G is bipartite if V(G) = V1 ∪ V2 (G is split in two) such that:
- V1 ∩ V2 = ∅; they don’t have shared vertices
- E(G) ⊆ {⟨u, v⟩ | v1 ∈ V1 and v2 ∈ V2 }; any edge of G must connect a vertex from V1 to one of V2.
• Bipartite graphs are often drawn as ranked embeddings. This will make it more obvious to say
whether a graph is bipartite or not. A ranked embedding is made as follows:
- Choose a vertex and put all the vertices where they’re connected to through an edge in a
horizontal row above. Do the same with those vertices until all vertices are in a row.
- If all the vertices on the same row do not have an edge connected them, the graph is bipartite.
- The number of rows is the number of possible disjoint subsets.
➤2.11 Planar Graphs & Euler’s Formula
• A simple and connected graph is planar if there exists a drawing in the 2D plane such that no two
edges cross.
• In any planar graph of n ≥ 1 vertices, m ≥ 0 edges and r ≥ 1 regions (regions closed off because of
edges and vertices, including the exterior region), then n − m + r = 2. This is the Euler’s formula.
• For any planar graph G with n ≥ 3 vertices and m edges: m ≤ 3n − 6.
• Every planar graph G has at least one vertex v with δ(v) ≤ 5.
2
