Problem Set 10: Graphs

sz11233
CS/MATH 113 Discrete Mathematics
Habib University
Spring 2026

Problems
In the following problem set assume all the graphs are simple and finite unless specified otherwise.
1. In parkour civilization everything is parkour. For some positive integer m there are at most
2m + 1 houses at the parkour pro level of parkour civilization. From each house you can
parkour to exactly m other houses. Every parkour pro is sleeping inside a house. Tung Tung
Tung Sahur wants to wake up all the parkour pros. For this he wishes to parkour to each of
the houses in parkour civilization. By the help of Agent 5.5 he can teleport to any one house
of his choice by then from there he would have to parkour to every other house he wishes to
visit. Can Tung Tung Tung Sahur visit every house and wake up every parkour pro? Give
a formal proof for your answer.

Figure 1: Tung Tung Tung Sahur [Link]

Solution: Let each house be a vertex and each parkour connection be an edge. Every
vertex has degree m and total vertices n ≤ 2m + 1.
Consider a longest path in the graph. Let its endpoint be v.

1
CS/MATH 113 2026 Pset 10: Graphs sz11233

Since v has m neighbors and the path is maximal, all neighbors of v must already lie on
the path. This forces the path to include all vertices.
So the graph contains a Hamiltonian path, meaning Tung Tung Tung Sahur can visit
every house.

2. In this problem we will prove/disprove some basic results regarding existence of cycles and
paths in a graph.
(a) Prove or disprove that a forest with n vertices and m components will always have n−m
edges.

Solution: A forest is a collection of trees. Each tree with ni vertices has ni − 1

edges.
So total edges: X X 
(ni − 1) = ni − m = n − m

Hence every forest with n vertices and m components has n − m edges.

(b) Prove or disprove that every n-vertex graph with at least n edges contains a cycle.

Solution: A graph with n vertices and at least n edges cannot be a forest.

Since a forest has at most n − 1 edges, the extra edge must create a cycle.

(c) Prove that every graph G contains a path of length atleast δ(G) where δ(G) represented
the smallest degree of a vertex in G.

Solution: Let P be a longest path and let v be an endpoint.

All neighbors of v must lie on P , otherwise we can extend the path.
So the length of P is at least d(v) ≥ δ(G).

(d) Prove that every graph G with δ(G) ≥ 2 contains a cycle of length at least δ(G) + 1,
where δ(G) represented the smallest degree of a vertex in G.

Solution: Let P be a longest path with endpoint v.

Since δ(G) ≥ 2, vertex v has at least two neighbors on the path.
This creates a cycle containing at least δ(G) + 1 vertices.

3. In this problem we will see how a lot of our theorems and intuition breaks when it comes to
infinite graph. An infinite graph is a graph where the set the vertices is an infinite set.
(a) Show that if G is a finite graph such that every vertex of G has a degree of 2 then G
contains a cycle.

Solution: In a finite graph where every vertex has degree 2, start from any vertex
and follow edges.

Page 2 of 7
CS/MATH 113 2026 Pset 10: Graphs sz11233

Since degree is always 2, we cannot stop or branch, so we must eventually return

to a visited vertex.
Thus a cycle exists.

(b) Show that this isn’t necessarily true if G is an infinite graph.

Solution: This statement is not true for infinite graphs.

Consider the infinite path:

· · · v−2 − v−1 − v0 − v1 − v2 · · ·

Every vertex has degree 2, but there is no cycle because the graph never closes back
on itself.

(c) Construct an infinite graph G such that every vertex of G has a degree of 2 and G
contains a cycle.

Solution: We can construct an infinite graph where every vertex has degree 2 and
cycles exist.
For example, take a disjoint union of cycles:

C3 ∪ C 4 ∪ C 5 ∪ · · ·

This graph is infinite, every vertex has degree 2, and each component contains a
cycle.

4. With some stroke of luck you finally were able to take some time out of your Habib schedule
and manage to make it to an Eid dawat. There were n people at the dawat no two people
are of the same age. After 4 years of missing every event due to some assignment being
due, you were shocked to see people giving each other Eidi. But sadly discrete maths made
a permanent damage to your brain, instead of enjoying the event you were wondering how
many times Eidi was given. You notices that every one gave Eidi to everyone who is younger
than them but didn’t gave it to anyone older than them. How many times Eidi was given?
Find a closed form formula in terms of n and given a formal proof for your answer.

Solution: Every pair of people with different ages contributes exactly one Eidi transfer
(older to younger).
So total number of transfers is:
 
n n(n − 1)
=
2 2

5. In the year 3025 fascism is at the rise in the galactic empire. Political alliances are being
formed. You as rebels want to break these alliances to kill off these ideologies before they take
over every corner of the galaxy. A faction is a group of people who have political alliances

Page 3 of 7
CS/MATH 113 2026 Pset 10: Graphs sz11233

with each other. For example if Kirk is in alliance with Reinhard and Reinhard is in alliance
with Paul then Kirk, Reinhard and Paul are in the same faction (even though Kirk and Paul
are not in alliance themselves). Given any faction you want to break it into smaller factions.
Your rebel forces captain Khubaib is a pacifist he thinks the best way to break these factions
is to talk to people so that they break the alliance with some one. Khubaib is a master at
persuasion he can talk to anyone convince them to break one of their alliances (in order for
them to break more alliances Khubaib will have to talk to them again). Figure 2 shows an
example of this. Let P be the smallest number of times Khubaib has to talk to someone to
break a faction. Munawar, who is the second in command in the rebels on the other hand
knows how these factions work, by the time you guys are able to break a faction they would
have already increased in size. He suggests to eliminate the people from factions (with any
means necessary) so the faction breaks into smaller factions. Figure 3 shows an example of
this. Let Q be the smallest number of people you have to eliminate in order to break the
faction.
(a) You act as an arbitrator between Khubaib and Munawar. Prove or disprove that P ≥ Q.
(b) You now want to take an idea about how many people are in each faction. A chain
in a faction is a series of people s1 , s2 , . . . sn such that each person si is in alliance
with person si+1 and s1 is in alliance with sn for each i ∈ [n − 1]. With your spies
you have been able to find out that the smallest chain in any faction is of 4 people.
And that everyone in each faction is in alliance with at least m people. Sadly your
spies were caught and they weren’t able to deliver back any more information. But you
studied Discrete Mathematics from Habib University a 1000 years ago so for you this
information is sufficient. Prove or disprove that there are at least 2m people in each
faction.

Solution: Removing a person eliminates all their connections at once, while Khubaib
removes only one alliance per action.
So removing a person is always at least as effective as breaking alliances one by one.
Hence:
P ≥Q

Now, each person has at least m alliances and no cycle in a faction has length less than
4.
This means neighbors of a vertex cannot be too tightly connected, so each level around
a person expands significantly.
Counting gives:
n ≥ m2 + 1

Since m2 + 1 ≥ 2m for all m ≥ 1, every faction has at least 2m people.

6. Let G and H be some graphs. Show that G ∼

= H ⇐⇒ G ∼
=H

Solution: An isomorphism preserves adjacency and non-adjacency.

So the same mapping also works for complements.

Page 4 of 7
CS/MATH 113 2026 Pset 10: Graphs sz11233

Original Faction Structure Faction Structure after Khubaib talks to Reinhard.

Rein Rein
hard hard

Kirk Paul Kirk Paul

Figure 2: Kirk is in alliance with Reinhard and Reinhard is in alliance with Paul. So Kirk,
Reinhard and Paul form a faction. On the left we have the original faction structure then on
right we have the faction structure after Khubaib talks to Reinhard and convince him to break
his alliance with Paul.

Original Faction Structure Faction Structure after Munawar eliminates Reinhard.

Rein
hard

Kirk Paul Kirk Paul

Figure 3: Kirk is in alliance with Reinhard and Reinhard is in alliance with Paul. So Kirk,
Reinhard and Paul form a faction. On the left we have the original faction structure then on
right we have the faction structure after after Munawar eliminates Reinhard.

Hence:
G∼
= H ⇐⇒ G ∼
=H

7. Show that a vertex c in a connected simple graph G is a cut vertex if and only if there are
vertices u and v, both different from c, such that every path between u and v passes through
c.

Solution: If c is a cut vertex, removing it disconnects the graph, so there exist u, v such
that every path between them passes through c.
Conversely, if all paths between u and v go through c, removing c disconnects the graph.
So the statement holds both ways.

8. For this problem, we recommend drawing out some graphs to build your intuition then give
a constructive proof.

Page 5 of 7
CS/MATH 113 2026 Pset 10: Graphs sz11233

Definition 1. Let G = (V, E) be a graph. A decomposition of G is a list of subgraphs of G

(obtained from removing edges of G) such that each edge appears in exactly one subgraph in
the list. Figure 4 shows an example of graph decomposition.

Figure 4: An example of decomposition of K5 into two C5 s.

Prove that for any n ∈ Z+ \ {1, 2} the graph Kn can be decomposed into three isomorphic
subgraphs if and only if n + 1 is not divisible by 3.

Solution: Total edges in Kn are:

n(n − 1)
2
For decomposition into 3 isomorphic subgraphs, this must be divisible by 3.
This gives:
n + 1 ̸≡ 0 (mod 3)

So decomposition is possible iff n + 1 is not divisible by 3.

9. In the film Good Will Hunting, a “difficult” math problem that Matt Damon’s character
Will Hunting is seen solving is the following:
Draw all possible 10 vertices tree that have no vertex of degree 2.
But it turns out this problem is not so difficult after all. Solve the problem from Good Will
Hunting.

Solution: A tree with 10 vertices has 9 edges.

Let L be leaves and I internal vertices:

L + I = 10

Since no vertex has degree 2, internal vertices have degree at least 3.

This gives:
L≥I +2

So possible cases are:

(L, I) = (6, 4), (7, 3), (8, 2), (9, 1)

These are all valid trees with no degree-2 vertices.

Page 6 of 7
CS/MATH 113 2026 Pset 10: Graphs sz11233

Figure 5: Will Hunting solving the problem, you can build on the partial solution visible on the
here.

Page 7 of 7