Graph Theory: Structures and Connectivity

Graphs provide a formal framework for modeling relationships between discrete objects. A graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E$ .

Fundamental Properties

Degree: The number of edges connected to a vertex.
Handshaking Lemma: $\sum_{v \in V} \text{deg}(v) = 2|E|$ .

Interactive Lab

def get_degrees(adj_list):
  return {node: len(neighbors) for node, neighbors in adj_list.items()}

# Adjacency List representation
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
}

degrees = get_degrees(graph)
print(f"Degrees: {degrees}")
print(f"Sum of degrees: {sum(degrees.values())}")
print(f"Edges count (Sum/2): {sum(degrees.values()) // 2}")

python

1def get_degrees(adj_list):

2 return {node: len(neighbors) for node, neighbors in adj_list.items()}

4# Adjacency List representation

5graph = {

6 'A': ['B', 'C'],

7 'B': ['A', 'D', 'E'],

8 'C': ['A', 'F'],

9 'D': ['B'],

10 'E': ['B', 'F'],

11 'F': ['C', 'E']

12}

14degrees = get_degrees(graph)

15print(f"Degrees: {degrees}")

16print(f"Sum of degrees: {sum(degrees.values())}")

17print(f"Edges count (Sum/2): {sum(degrees.values()) // 2}")

Connectivity and Traversal

Connected: A path exists between every pair of vertices.
Cycle: A path that starts and ends at the same vertex.

Interactive Lab

def find_path(graph, start, end, path=[]):
  path = path + [start]
  if start == end: return path
  for node in graph[start]:
      if node not in path:
          newpath = find_path(graph, node, end, path)
          if newpath: return newpath
  return None

print(f"Path from A to F: {find_path(graph, 'A', 'F')}")

python

1def find_path(graph, start, end, path=[]):

2 path = path + [start]

3 if start == end: return path

4 for node in graph[start]:

5 if node not in path:

6 newpath = find_path(graph, node, end, path)

7 if newpath: return newpath

8 return None

10print(f"Path from A to F: {find_path(graph, 'A', 'F')}")

Planar Graphs and Euler’s Formula

A graph is planar if it can be drawn without edges crossing. For a connected planar graph: $V - E + F = 2$ where $F$ is the number of faces.

A connected graph with 6 vertices and 10 edges is planar. How many faces does it have?

Special Graphs: Trees and Bipartite Graphs

Tree: A connected graph with no cycles. A tree with $n$ vertices always has $n-1$ edges.
Bipartite: Vertices can be partitioned into two sets such that no edge exists within a set.

Interactive Lab

def is_bipartite(graph):
  color = {}
  for node in graph:
      if node not in color:
          stack = [(node, 0)]
          color[node] = 0
          while stack:
              u, c = stack.pop()
              for v in graph[u]:
                  if v in color:
                      if color[v] == c: return False
                  else:
                      color[v] = 1 - c
                      stack.append((v, 1 - c))
  return True

print(f"Is graph bipartite? {is_bipartite(graph)}")

python

1def is_bipartite(graph):

2 color = {}

3 for node in graph:

4 if node not in color:

5 stack = [(node, 0)]

6 color[node] = 0

7 while stack:

8 u, c = stack.pop()

9 for v in graph[u]:

10 if v in color:

11 if color[v] == c: return False

12 else:

13 color[v] = 1 - c

14 stack.append((v, 1 - c))

15 return True

17print(f"Is graph bipartite? {is_bipartite(graph)}")

Famous Theorems

Four Color Theorem: Any planar graph can be colored with 4 colors.
Kuratowski’s Theorem: A graph is planar iff it doesn’t contain $K_5$ or $K_{3,3}$ .

Graph Theory

Graph Theory: Structures and Connectivity

Fundamental Properties

Connectivity and Traversal

Planar Graphs and Euler’s Formula

A connected graph with 6 vertices and 10 edges is planar. How many faces does it have?

Special Graphs: Trees and Bipartite Graphs

Famous Theorems

What is a tree in graph theory?