CSC111 Tutorial 8: More with Graphs
In lecture this week, we continued our study of graphs by looking at cycles and trees. In this tutorial,
you’ll get some more practice working with graphs, both by doing some more proofs on graphs and
writing some code.
Part 1: Proofs on graphs
1. In lecture, we proved that every non-empty tree satisfies . Our proof relied on the
fact that if we remove a degree-one vertex from the tree, the remaining vertices are still connected
Your first task is to prove this statement.
a. Let , and let be an arbitrary path in , with .
Prove that for all , .
b. Let be a tree, and let be a vertex with . Prove that the graph
obtained by removing from is connected.
2. Prove that any connected graph with at least three vertices has a vertex with degree .
Hint: you can prove this by contradiction.
Part 2: Bipartite graphs
Now, let’s introduce one new definition that is central to many applications of graphs.
Definition. Let be a graph. We say that is bipartite when it satisfies the following
properties:
There exist subsets such that , , and and form a partition of . Th
is, and .
|E| = |V | − 1
G = (V , E) v0, v1, v2,…, vk G k ≥ 2
i ∈ {1, 2,…, k − 1} d(vi) ≥ 2
G = (V , E) v ∈ V d(v) = 1
v G
≥ 2
1
G = (V , E) G
V1, V2 ⊂ V V1 ≠ ∅ V2 ≠ ∅ V1 V2 V
V1 ∪ V2 = V V1 ∩ V2 = ∅
3/25/2021 CSC111 Tutorial 8: More with Graphs
https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 2/5
Every edge in has exactly one endpoint in and one in (Equivalently, no two vertices in
are adjacent, and no two vertices in are adjacent).
When is bipartite, we call the partitions and a bipartition of .
Tip: bipartite graphs are typically drawn such that and are clearly separated (e.g., with all the
vertices of on the left, and all the vertices of on the right).
1. To make sure you understand the definition of bipartite graphs, identity which of the following ar
bipartite graphs.
2. Show that the following graph is bipartite by finding a bipartition of .
E V1 V2 V1
V2
G V1 V2 G
V1 V2
V1 V2
G = (V , E) G
V = {1, 2, 3, 4, 5, 6} and E = {{1, 2}, {1, 6}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}
3/25/2021 CSC111 Tutorial 8: More with Graphs
https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 3/5
3. Finally, let’s develop an algorithm for computing a bipartition of a graph. Not surprisingly, we can
use the same recursive traversal approach as _Vertex.check_connected, but need to be a bit
clever in how we keep track of which vertices are in which of the partitioned sets.
Download tutorial8_part2.py (starter-files/tutorial8_part2.py) and implement the method
_Vertex.compute_bipartition according to its specification. We’ve provided a few hints in that
file, but this is a fairly complex function to implement, so we strongly encourage you to speak with
your classmates and TAs to share ideas!
After you’re done, complete the method Graph.bipartition to compute a bipartition of a graph.
(As usual, this method will be fairly short, as it should mainly just call the corresponding _Vertex
method.)
Part 3: Visualizing graphs
As our send-off to graphs, we’ll end by exploring how to visualize graphs using a few different
approaches.
1. First, download tutorial8_part3.py (starter-files/tutorial8_part3.py) and open it. Inside, we’ve
provided a fresh copy of the _Vertex and Graph class, and some pygame-related helper functions
that take care of the Pygame window setup for you.
Your task is to complete the method Graph.draw. To do so, you’ll need to review the pygame
functions:
pygame.draw.circle (https://www.pygame.org/docs/ref/draw.html#pygame.draw.circle)
pygame.draw.line (https://www.pygame.org/docs/ref/draw.html#pygame.draw.line)
After you’ve completed this method, test it by running the provided visualize_graph function o
some graphs of your choice. You can use the small ones from lecture or tutorial, or randomly
generate your own graphs! Here are two examples we created, both with 100 vertices and 150
randomly-chosen edges.
3/25/2021 CSC111 Tutorial 8: More with Graphs
https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 4/5
2. As you might have realized in completing the previous task, deciding how to positions vertices in
graph isn’t a straightforward task. While we can certainly choose vertex locations in a variety of
ways, it becomes much harder to do so if we want to keep neighbours closer to each other. So in
this final exercise of this tutorial, you’ll explore using a Python library to run a graph layout
algorithm that chooses vertex positions based on the structure of the graph.
a. First, install the new Python libraries networkx, numpy, and scipy. (In PyCharm, open the
Settings/Preferences window and go to “Project: csc111 -> Project Interpreter” and click on
the “+” icon.)
b. After everything has been installed, uncomment the import networkx line at the top of the
Python file and implement the method Graph.draw_nx, following our instructions.
c. Test your work with the visualize_graph_nx function. Try creating a graph with two
separate components (we did this by randomly generating edges between the first 50 vertice
then the last 50 vertices). The graph layout algorithm from networkx produces a graph that
separates these components:
2
3
3/25/2021 CSC111 Tutorial 8: More with Graphs
https://www.teach.cs.toronto.edu/~csc111h/winter/tutorials/08-graphs-more/ 5/5
Further exploration
The networkx library provides several different graph layout algorithms, which you can see on its onlin
documentation (https://networkx.org/documentation/stable/reference/drawing.html#modulenetworkx.drawing.layout).
Try playing around with these!
If you’re interested in graph visualization more generally, you can check out the Graph drawing
Wikipedia page (https://en.wikipedia.org/wiki/Graph_drawing) as a starting point for further reading
Additional exercises
1. Prove that for every graph , if has a cycle of odd length, then is not bipartite.
1. For example, the book review graphs you’re using on Assignment 3 are bipartite, with the two
partitions being the set of “user” vertices and “book” vertices.↩
2. You’ll also be installing and using these libraries for Assignment 3!↩
3. nx is a common short form for the networkx library.↩
4. In fact, the converse of this statement is also true (so it’s an if and only if), but the converse is
harder to prove.↩
G = (V , E) G G 4