Summary of the slides of Jacopo Urbani and Ali Mehrabi based on the book "Graph Theory and Complex Networks" by Maarten van Steen.
It discusses chapters 2, 3, 4, 5, 6, 7, and 9.
*Study material of following years may differ*
➤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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller syntryx. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.95. You're not tied to anything after your purchase.
