Graph Theory, Part I

UCLA Math Circle Advanced 1B

by Jack Fasching
Week 3: October 13, 2024

1 Introduction to Graph Theory

Definition 1.1 In mathematics, a graph G is an ordered pair (V(G), E(G)),

comprised of V(G), a set of vertices, and E(G) ⊆ {{x, y} | x, y ∈ V(G) and x ̸= y}, a set of edges.

Definition 1.2 We define an edge e in a graph G as an unordered pair of vertices {x, y}, where
x, y ∈ V(G) and x ̸= y (that is, an edge is associated with two distinct vertices). We say vertices x, y
are the edge’s endpoints. We also say e joins x and y and is incident to each of the vertices.

For example, the graph below has four vertices, A, B, C, and D, and four edges, e1 = {A, B},
e2 = {A, C}, e3 = {B, C}, and e4 = {C, D}:

e2

e1 e3 e4
A B C D

Definition 1.3 The degree d(vi ) of a vertex vi of a graph is the number of the edges in a graph
incident to the vertex (in other words, if vi is one of the edge’s vertices).

In the example above, d(A) = 2, d(B) = 2, d(C) = 3, and d(D) = 1.

1
 IMPORTANT: When drawing a graph, we depict the vertices as dots or circles, and depict the
edges as lines or curves connecting joined vertices, similar to our example graph. Naming the vertices
and edges is optional.

Problem 1.1 Draw the following:

• A graph with 5 vertices, each having a degree of 2

• A graph with 6 vertices, each having a degree of 3
• A graph with 4 vertices, each having a degree of 1

Problem 1.2 Can you draw a graph with 5 vertices, each having a degree of 3? Why or why not?

Theorem 1.1 On any graph, the sum of the degrees of the vertices equals twice the number of edges.

Problem 1.3 Prove Theorem 1.1.

Corollary 1.1.1 The number of vertices of odd degree in any graph is even.

Problem 1.4 Prove Corollary 1.1.1.

Problem 1.5 If 10 people come to a party, and everybody shakes hands with everyone else exactly once,
how many handshakes take place? What if there are n people? Solve this problem using combinatorics,
then using Corollary 1.1.1.

If we made a graph of this scenario, we would have a complete graph– where every vertex shares
an edge with every other vertex. This means G is a complete graph if and only if
E(G) = {{x, y} | x, y ∈ V(G) and x ̸= y}.

2
 Figure 1: The seven bridges of Königsberg, circled for convenience.

Problem 1.6 There are 8 students from Cauchy Academy and 7 students from Schwarz High. Each
student from Cauchy Academy has a one-on-one study session with each student from Schwarz High.
We want to know how many individual study sessions take place in total. What if there are m students
from Cauchy Academy and n students from Schwarz High? Solve this problem using combinatorics,
then using Corollary 1.1.1.

If we made a graph of this scenario, we would have a bipartite graph– where every vertex in a
set shares an edge with every other vertex in its opposite set, but not with the vertices in its own.

2 Eulerean Paths and Königsberg

Definition 2.1 A graph G′ is a subgraph of graph G if V(G′ ) ⊆ V(G) and E(G′ ) ⊆ E(G) (in other
words, G′ is only made of vertices and edges from G).

Definition 2.2 A path in a graph is a subgraph whose vertices can be numbered v1 , v2 , ..., vn , vn+1 so
that e1 = {v1 , v2 }, e2 = {v2 , v3 }, ..., en = {vn , vn+1 }. The length of a path is the number of edges it
has (in this case, n). A cycle is a path with v1 = vn+1 (making it closed).

Definition 2.3 A graph is connected if any vertex is connected to any other vertex by some path.

Definition 2.4 A path in a graph is Eulerean if it visits every edge in the graph exactly once.

Problem 2.1 Find three different Eulerean paths in our first example of a graph (list the vertices of
each path).

Eulerean paths are named after the famous Swiss mathematician Leonard Euler, who developed
graph theory after being intrigued by an old problem involving the city of Königsberg. The river Pregel
divides Königsberg into four separate land masses connected by seven bridges, as seen in Figure 1.

3
 The problem went like this: is it possible to walk around the city crossing each of the bridges exactly
once? There is an image of Königsberg below if you want to try and find a solution.

The problem seems impossible, but how do we know for sure? To answer this, let’s convert the map
into a graph, with land masses represented by vertices and bridges represented by edges. A solution
to the puzzle is an Eulerean path in the graph. However, we soon encounter a problem.

Problem 2.2 Why can’t we make a graph from the bridge of Königsberg this way? From this, what
general rule about constructing graphs can we make?

4
 Since we can’t use Königsberg, let’s look at 3 examples that are graphs below.

Problem 2.3 For each graph, determine if an Eulerean path exists. On each of its vertices write its
degree. Do you see a pattern emerge?

Problem 2.4 How can you prove if an Eulerean path exists on each graph or not?

However, to apply this to our ”graph” of Königsberg, we must create a new definition of what this
”graph” is:

Definition 2.5 In mathematics, a multigraph G is an ordered triple (V(G), E(G)), ϕG ),

comprised of V(G), a set of vertices, E(G)), a set of edges, and ϕG : E → {{x, y}|x, y ∈ V(G) and x ̸=
y}, an incidence function mapping every edge to an unordered pair of vertices.

Definition 2.6 Two edges e1 and e2 in a multigraph are multiple edges if ϕG (e1 ) = ϕG (e2 ).

For multigraphs, we define degree, path, cycle, and Eulerean path the same as for regular
graphs.

Problem 2.5 Can we make a multigraph out of Königsberg? Why does it work through this definition?

5
Problem 2.6 For the multigraph of Königsberg, Write the degree on each of its vertices.

Problem 2.7 Does our answer for Problem 2.4 determine if an Eulerean path exists on a multigraph?

Problem 2.8 Is the Königsberg bridge problem impossible? Why or why not?

3 Planar Graphs and Euler’s Equation

In this section, we will deal with graphs that are connected, and not multigraphs (that is, there is at
most one edge between any two vertices).
With that out of the way, here’s another graph-related puzzle:

There are three houses (labeled 1, 2, and 3) and three utility plants that produce water, electricity,
and gas (labeled W, E, and G respectively). Draw paths (not necessarily in straight lines) connecting
the houses to each of the utility plants such that no two paths intersect:

1 2 3

W E G

Similar to the Königsberg bridges before, this problem is impossible because the bipartite graph
we are attempting to make, called K3,3 :

6
 cannot be drawn without overlapping edges.

Definition 3.1 A graph is planar if it is connected and can be drawn with edges that do not overlap.

Problem 3.1 Redraw the following graphs without intersecting edges to show they are planar:

Definition 3.2 A face on a graph is an area divided by the edges of a graph. This includes interior
faces as well as an exterior face, the area around the graph.

For example, the following graph has 3 faces:

For the next problems, let V (G) = the number of vertices a graph G has, E(G) = the number of
edges, and F (G) = the number of faces.

Definition 3.3 A connected graph is a tree if it contains no cycles.

Problem 3.2 Prove that, for every tree G, V (G) = E(G) + 1.

7
Problem 3.3 Prove that, for every cycle G, V (G) = E(G).

Definition 3.4 The Euler characteristic of a graph G is equal to χ(G) = V (G) − E(G) + F (G).

Problem 3.4 Find the Euler characteristics of the two graphs in Problem 3.1.

Definition 3.5 A subgraph of G is a spanning tree if it contains all vertices in G while only con-
taining edges from G .

Theorem 3.1 (Euler’s Formula) The Euler characteristic of every finite planar graph is 2.

Problem 3.5 Prove Theorem 3.1.

IMPORTANT: If you think you have found a graph without intersecting edges that contradicts
Theorem 3.1, remember that planar graphs must be connected and not be a multigraph.

Problem 3.6 Prove that the complete graph containing five vertices K5 is non-planar.

Problem 3.7 Prove that the complete graph containing five vertices K5 is non-planar.

8
Problem 3.8 What is the minimum number of vertices needed for a non-planar graph?

Problem 3.9 Prove that the graph K3,3 is non-planar.

Problem 3.10 Imagine that, instead of looking at graphs on a flat plane, we were looking at them on
the surface of a torus (like a ring-shaped donut) shown below. On each torus, find a way to draw K5
and K3,3 without their edges intersecting.

9
4 Challenge Problems (not for the faint of heart)

Problem 4.1 In the country of Jetlaggia it is possible to travel by air between any two of the main
cities; if there is not a direct flight there is at least an indirect flight passing through other cities on
the way. A path is an air route between two different cities that passes through no intermediate (or
start or end) city more than once. The length of a path is the total number of cities on it, counting its
endpoint but not its starting point. Let M be the maximum of all path lengths in Jetlaggia. Prove that
any two paths of length M must have at least one city in common.

Problem 4.2 How many people do we need to have at a party to ensure that there are always at least
3 people all of whom know each other, or three people none of whom know each other? What if 3 is
changed to 4?

Problem 4.3 A set of 1990 people is divided into non-intersecting subsets in such a way that:

1. No one in a subset knows all the others in the subset.

2. Among any 3 people in a subset there are always at least 2 who do not know each other.
3. For any 2 people in a subset who do not know each other, there is exactly 1 person in the same
subset knowing both of them.

Prove that within each subset every person has the same number of acquaintances. What is the maxi-
mum possible number of subsets?

10