Basic Graph Questions

1. The handshake lemma

In an undirected graph with vertices V and edges E, what’s the sum of all degrees? Why?

2. Convert representations

Given this edge list, build both the adjacency list and the adjacency matrix:

Edges:  [(0,1), (0,2), (1,2), (2,3)]      (undirected, 4 vertices)

3. Model this problem as a graph

You’re given a list of flights as tuples (from_city, to_city, cost). What’s the graph?

4. Spot the cycle

Is the following directed graph a DAG (directed acyclic graph)?

Edges: [(A→B), (B→C), (C→D), (D→B)]

5. Bipartite by inspection

Is this graph bipartite? Can you split the vertices into two groups such that every edge connects a vertex in one group to a vertex in the other?

Vertices: {1, 2, 3, 4, 5, 6}
Edges:    {(1,4), (1,5), (2,4), (2,6), (3,5), (3,6)}

6. Count connected components

This adjacency list represents an undirected graph. How many connected components does it have?

0 → [1]
1 → [0]
2 → [3]
3 → [2]
4 → []
5 → [6]
6 → [5]