MATH-UA 120 Discrete Mathematics:

Problem Set 9
Queen Elizabeth
Due Friday, December 13th, 2024

Assignment Instructions
• These are to be written up in LATEX and turned in on Gradescope.
• Click here to duplicate this .tex file in Overleaf .
• Write your solutions inside the solution environment.
• You are always encouraged to talk problems through with your peers and your instructor, but your
write up should be done independently.

• Problems are graded on correctness and fluency.

• Unless stated otherwise, all calculations require justification.
• Some tutorials on how to use LATEX can be found here. If you have any questions about LATEX
commands you can always ask your instructor for advice.

Statement on generative AI
In this and other mathematics courses, you are expected to construct clear and concise mathematical argu-
ments based on statements proven in our text and class notes. Large language models such as ChatGPT
are unable to produce this kind of solution. They also frequently generate circular logic and outright false
results.
You may use AI to summarise content, generate study plans, create problems, or do other study-related
activities. You may not ask a chatbot to solve your quiz or homework problems, or do any assessment-related
activities.
You may use AI tools to edit your grammar and punctuation, but remember that mathematical English
is not the same as academic English in other disciplines.

1
Problem 1
Let G and H be graphs. We say that G is isomorphic to H if there is a bijection from f : V (G) −→ V (H)
such that for all a, b ∈ V (G) we have a ∼ b, in G, if and only if f (a) ∼ f (b), in H. The function f is called
an isomorphism from G to H.
a) Prove that isomorphic graphs have the same number of vertices.

b) Prove that if f : G −→ H is an isomorphism and v ∈ V (G), then the degree of v in G is equal to the
degree of f (v) in H.
c) Prove that isomorphic graphs have the same number of edges.

(a)
If f : V (G) → V (H) is an isomorphism, it is a bijection. A bijection means that ff is a one-to-one
correspondence, therefore,
|V (G)| = |V (H)|.
(b)
Let f : V (G) → V (H) be an isomorphism, and v ∈ V (G). The neighbors of v in G are:

NG (v) = {u ∈ V (G) | u ∼ v}.

Since f preserves adjacency (u ∼ v ⇐⇒ f (u) ∼ f (v)), we have:

NH (f (v)) = {f (u) | u ∈ NG (v)}.

As f is bijective, |NG (v)| = |NH (f (v))|, so:

degG (v) = degH (f (v)).

(c)
The edge sets of G and H are:

E(G) = {{u, v} | u ∼ v}, E(H) = {{f (u), f (v)} | u ∼ v}.

Since f induces a bijection between edges,

|E(G)| = |E(H)|.

On the other hand, by Thm 47.5, for every vertex v of G, v, f (v) have the same degree, therefore G, H
have the same number of edges.

2
Problem 2
Suppose G is a subgraph of H. Prove or disprove:
a) α(G) ≤ α(H)
b) ω(G) ≤ ω(H)

(a)
This is not true. We give a counterexample.
Define H: Let H be a graph with two vertices v1 and v2 , connected by an edge {v1 , v2 }. In this graph,
the largest independent set can only consist of one vertex (since v1 and v2 are adjacent). Thus:

α(H) = 1.

Define G: Let G be a subgraph of H that has the same two vertices v1 and v2 , but with the edge {v1 , v2 }
removed (so G is an edgeless graph). In this case, the entire vertex set {v1 , v2 } is an independent set, because
there are no edges in G. Thus:
α(G) = 2.
Although G is a subgraph of H, we still have α(G) = 2 ≥ α(H).
(b)
A clique in G is a set of vertices S ⊆ V (G) such that every pair of vertices in S is adjacent in G. Since
E(G) ⊆ E(H), any clique S in G is also a clique in H (because adjacency in G implies adjacency in H).
Therefore, the largest clique in G cannot exceed the largest clique in H, i.e.,

ω(G) ≤ ω(H).

3
Problem 3
Let G = (V, E) be a graph with V = {v1 , v2 , . . . , vn }. Its degree sequence is the list of degrees of its
vertices, arranged in non-increasing order. That is, the degree sequence of G is (d(v1 ), d(v2 ), . . . , d(vn )) with
the vertices arranged such that d(v1 ) ≥ d(v2 ) ≥ · · · ≥ d(vn ). Below are different lists of possible degree
sequences. Determine whether each case can be a graph with n vertices. If not, explain why not. If so,
describe a graph with these degrees: Is it a complete graph? A cycle? A path? Does it contain any specific
subgraphs? Is it connected? etc..

a) n = 7 and (6, 5, 4, 3, 2, 1, 0)
b) n = 6 and (2, 2, 2, 2, 2, 2)
c) n = 6 and (3, 2, 2, 2, 2, 2)

d) n = 6 and (1, 1, 1, 1, 1, 1)
e) n = 6 and (5, 3, 3, 3, 3, 3)

(a) n = 7 and (6, 5, 4, 3, 2, 1, 0)

The largest degree is 6, which means the vertex with degree 6 must be connected to all other 6 vertices.
However, the vertex with degree 0 has no connections to other vertices, making it impossible for the vertex
with degree 6 to be adjacent to all vertices.
This degree sequence cannot correspond to a graph because the vertex with degree 6 cannot exist alongside
a vertex with degree 0.
(b) n = 6 and (2, 2, 2, 2, 2, 2)
All vertices have degree 2, meaning each vertex is connected to exactly two other vertices. This is possible
if the graph forms a cycle of 6 vertices. We give an example.

V (G) = {1, 2, 3, 4, 5, 6}

E(G) = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 1}}
This is a cycle but not a path. This graph is connected,but not a complete graph.
(c) n = 6 and (3, 2, 2, 2, 2, 2) It is impossible. If it is a graph, Because of Thm 47.5 (3 + 2 + 2 + 2 + 2 + 2)/2
must be a integer. But evidently this is not true.
(d) n = 6 and (1, 1, 1, 1, 1, 1)
We give an example:

V (G) = {1, 2, 3, 4, 5, 6} E(G) = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}

This graph is a path. G is connected but not complete.

(e) n = 6 and (5, 3, 3, 3, 3, 3)
We give an example:
V (G) = {1, 2, 3, 4, 5, 6}
E(G) = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 6}, {3, 4}, {4, 5}, {5, 6}}
G is not a cycle or path, it is complete and connected.

4
Problem 4
Let G = (V, E) be a graph with V = {1, 2, 3, 4, 5, 6}. In the figures below we show the graphs (up to
isomorphism) of G − 1, G − 2 and so on, but we do not have the names on the vertices. The goal of this
problem is to reconstruct the graph G.

G−1 G−2 G−3

G−4 G−5 G−6

a) Determine the number of edges in G.

b) Using your answer in a) and the figures above, determine the degrees of each of the six vertices of G.
c) Determine G and sketch it.
There are instructions in the .tex file to help you draw the graph in LATEX.

(a)
G − 1, G − 2, G − 3, G − 4, G − 5, and G − 6 are the graphs obtained by removing a single vertex (and
its incident edges) from G.
The number of edges in G can be determined using the following relationship:
If the total number of edges in G is m, and removing a vertex reduces m by the degree of that vertex,
then:
Sum of all degrees of removed vertices = 2m
(this follows from the Thm 47.5).
From the figures, we count the number of edges in each G − i:
G − 1: 5 = m − deg(1) edges
G − 2: 4 = m − deg(2) edges
G − 3: 4 = m − deg(3) edges
G − 4: 4 = m − deg(4) edges
G − 5: 5 = m − deg(5) edges
G − 6: 6 = m − deg(6) edges
When a vertex is removed, the number of edges decreases by its degree. Therefore, the original number
of edges in G satisfies :
X
5 + 4 + 4 + 4 + 5 + 6 = 6m − deg(i) = 6m − 2m = 4m ⇒ m = 7

(b) Determine the degrees of each vertex:

Using the figures for G − i, the degree of a vertex i is the number of edges removed when i is removed.
Hence:
deg(1) = 2 (since G − 1 has 5 edges, so removing vertex 1 removed 2 edge).

5
 deg(2) = 3 (similar reasoning: G − 2 has 4 edges).
deg(3) = 3 (removing vertex 3 removed 3 edges, as G − 3 has 4 edges).
deg(4) = 3 (removing vertex 4 removed 3 edges).
deg(5) = 2 (removing vertex 5 removed 2 edge).
deg(6) = 1 (removing vertex 6 removed 1 edges).
Degrees of vertices:

deg(1) = 2, deg(2) = 3, deg(3) = 3, deg(4) = 3, deg(5) = 2, deg(6) = 1.

(c)
First, consider removing vertex 6 since vertex 6 is only connected to one other vertex. This is straight-
forward. Next, consider the positions of vertices 4 and 5, which requires analyzing the subgraph left after
removing vertices 4 and 5, respectively. Taking all factors into account, the original graph should look like
this.
V (G) = {1, 2, 3, 4, 5, 6}, E(G) = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {4, 6}}.

3 5

2 4

6
Problem 5
a) Given a graph with n vertices. First, what is the maximum number of edges can the graph have and be
disconnected? Then, what is the minimum number of edges we need to add to the previous graph to be
connected?
b) A complete bipartite graph Km,n is a graph whose vertices can be partitioned V = X ∪ Y such that
|X| = m and |Y | = n for positive integers m, n, and {x, y} is an edge in Km,n if and only if x ∈ X and
y ∈ Y . What is the number of edges in Km,n ?
c) Given a cycle graph C4 , how many possible subgraphs of C4 can there be?

(a)
To ensure the graph is disconnected, at least one vertex must remain isolated (degree 0).
For a graph with n vertices, the maximum number of edges in a disconnected graph is achieved by
connecting the remaining n − 1 vertices as a complete graph Kn−1 .
The number of edges in Kn−1 is:
 
n−1 (n − 1)(n − 2)
= .
2 2

To connect the isolated vertex to the rest of the graph, we need to add at least 1 edge between the
isolated vertex and any one of the other n − 1 vertices.
Therefore, the minimum number of edges to add is:

1.

(b)
A complete bipartite graph Km,n has two disjoint vertex sets X and Y , where:

|X| = m, |Y | = n.
Every vertex in X is connected to every vertex in Y .
The total number of edges in Km,n is:
m · n.
(c)
C4 is a cycle with 4 vertices and 4 edges, forming a closed loop. A subgraph is formed by choosing any
subset of vertices and any subset of edges among those vertices.
C4 has 4 vertices and 4 edges:
Total subsets of vertices: 24 = 16.
Total subsets of edges: 24 = 16.
It is possible to obtain new subgraphs by selecting a subset of edges and removing them, resulting in 16
cases.
Thus, the total number of possible subgraphs is:

16.

7
Problem 6
Prove that given a graph with exactly two vertices of odd degree, there must be a path joining these two
vertices.

If G is disconnected, consider its connected components:

The sum of the degrees of vertices in any connected component is even.
If u and v are in different components, then both components would need an odd number of vertices with
odd degree, contradicting Thm 47.5.
Therefore, u and v must belong to the same connected component of G.
If G is connected. In a connected graph, any two vertices within the same component are joined by a
path. Since u and v are in the same component. There exists a path between u and v.
In conclusion, if a graph has exactly two vertices of odd degree, there must exist a path joining these two
vertices.

8
Problem 7
Prove by induction on n: Given integer n ≥ 1, if T is a tree with n vertices, then T has n − 1 edges.

Base case when n = 1:

A tree with n = 1 vertex has no edges. The number of edges is n − 1 = 1 − 1 = 0, which holds true.
Assume that for a tree T with n = k vertices, the tree has n − 1 = k − 1 edges.
We need to prove that a tree T ′ with n = k + 1 vertices has n − 1 = k edges.
Start with T ′ , a tree with k + 1 vertices. By the definition of a tree, T ′ is connected and contains no
cycles.
Removing an edge from T ′ : Select any leaf (a vertex with degree 1) in T ′ and remove it along with its
incident edge.
The resulting graph T is still a tree (it remains connected and acyclic) and now has k vertices.
By the inductive hypothesis, the smaller tree T has k − 1 edges.
Adding the removed edge back to T to form T ′ :
The total number of edges in T ′ is k − 1 + 1 = k, which matches (k + 1) − 1 = k.
By induction, a tree T with n vertices always has n − 1 edges.

9
Problem 8
a) Prove that if a tree has n vertices where n ≥ 4 and is not a path graph Pn , then it has at least three
vertices of degree 1.
b) A complete bipartite graph Km,n is a graph whose vertices can be partitioned V = X ∪ Y such that
|X| = m and |Y | = n for positive integers m, n, and {x, y} is an edge in Km,n if and only if x ∈ X and
y ∈ Y . Prove that every cycle in Km,n has an even number of edges.

(a)
Assume a tree T with n ≥ 4 vertices is not a path graph Pn . We need to prove that T has at least three
vertices of degree 1.
Suppose, for the sake of contradiction, that T has at most two vertices of degree 1. Since T is a tree, it
must have at least one vertex of degree 1 (a leaf).
If T has exactly two vertices of degree 1, then T must be a path graph Pn , because in a path graph, the
two endpoints are the only vertices with degree 1, and all other vertices have degree 2.
This contradicts the assumption that T is not a path graph Pn .
Therefore, if T is not a path graph Pn , it must have at least three vertices of degree 1.
(b)
In a complete bipartite graph Km,n , the vertex set V is partitioned into two disjoint sets X and Y , where
|X| = m and |Y | = n. Edges only exist between vertices in X and Y , and there are no edges within X or Y .
Consider any cycle in Km,n . Let the cycle be v1 , v2 , . . . , vk , v1 .
Since Km,n is bipartite, vertices in the cycle must alternate between X and Y . That is, if v1 ∈ X, then
v2 ∈ Y , v3 ∈ X, and so on.
In order for the cycle to close (i.e., return to v1 after completing the cycle), the number of vertices in the
cycle must be even. Each edge alternates between X and Y , so there must be an equal number of transitions
from X to Y and from Y to X.
Therefore, every cycle in Km,n has an even number of edges.

10
Problem 9
Given a tree G with two vertices of degree 2, four vertices of degree 3, three vertices of degree 4, and the
remaining vertices of degree 1. How many vertices does G have?

Let n be the total number of vertices in the tree and k be the number of vertices with degree 1. From
the vertex classification, we know:
n = 2 + 4 + 3 + k,
which simplifies to:
n = 9 + k. (1)
The sum of the degrees of all vertices is:
X
deg(v) = 2 × 2 + 4 × 3 + 3 × 4 + 1 × k = 4 + 12 + 12 + k = 28 + k. (2)
v∈V

Using the property of trees that the sum of the degrees equals twice the number of edges, and the number
of edges is |E(G)| = n − 1, we have:
X
deg(v) = 2 · |E(G)| = 2 · (n − 1).
v∈V

Substitute n = 9 + k into this equation:

28 + k = 2 · ((9 + k) − 1).

This gives that

k = 12.
Therefore the amount of vertices is
n = 9 + 12 = 21.

11