CS2320 — Introduction to Graph Theory — 2025 (Jul-Nov)

Assignment 1

Release Date: 14/08/2025 Due Date: 19/08/2025 — 10:00 PM IST

Collaborator (if any): JAYANT MALVI.

Academic Integrity Statement: I, AARUSH, have not given or received any unauthorized help (from
any source: people, internet, etc.) on this assignment, and that I have typed each response on my own, and
in my own words.

The marks for each Exercise/Problem (1, 2, 3) are Fixed. However, the marks for each
Subproblem (1a, 1b, 2a, etc.) are Tentative — they may be changed during marking if
necessary.

The order of a graph G is its number of vertices and is generally denoted using n(G) := V (G), or simply n
(if the graph is clear from the context). The size of a graph G is its number of edges and is generally denoted
using m(G) := |E(G)|, or simply m.

1. [Degrees and Degree Sequences of Graphs] [11]

Given a graph G with vertices (ordered arbitrarily), say v1 , v2 , . . . , vn , we refer to the sequence
(d(v1 ), d(v2 ), . . . , d(vn )) as a degree sequence of G.

(a) For each of the following three connected graphs, write down its: (i) order n, (ii) size m, (iii) a
degree sequence, and (iv) the sum of degrees of all vertices: [6]

G1 G2 G3

Figure 1: Three connected graphs

Response:
G1 : (i) order n = 6 , (ii) size m = 9 , (iii) degree sequence can be {3, 3, 3, 3, 3, 3} , (iv) Sum of
degrees of all vertices is 18 .
G2 : (i) order n = 6 , (ii) size m = 5 , (iii) degree sequence can be {1, 1, 3, 2, 2, 1} , (iv) Sum of
degrees of all vertices is 10 .
G3 : (i) order n = 6 , (ii) size m = 14 , (iii) degree sequence can be {4, 5, 5, 5, 4, 5} , (iv) Sum of
degrees of all vertices is 28 .

(b) Recall that for a vertex v of a graph G, we use dG (v) or simply d(v) to denote the degree of v.
Your next goal is to prove the following lemma: [4]
 Lemma 0.1. For any graph G: X
d(v) = 2 · m
v∈V (G)

Response:
Proof 1 : Let’s denote total number of incidences as I .
Proof by Counting : We will calculate I using 2 different approaches and obviously both should be
equal .

Approach 1 - Contribution from vertex Vi to the counting of I will be equal to degree(Vi) ,Hence
I will be equal to sum of degree of each of the vertex .
P
that is I = v∈V (G) deg(v)

Approach 2 - Each edge adds 2 count to the number of Incidences and hence we can represent
I as : I = 2 ·m
Hence from equations from the 2 approaches , we can say that :
X
deg(v) = 2 · m
v∈V (G)

Hence Proved.

Proof 2 : We can use a simple argument that each and every edge contributes 2 to the count of
degree because there must be 2 vertices( 1 vertex in case of loops) associated with an edge and
that particular edge adds 1 to the count of degree of each of the 2 vertices ( In case of loop , it
adds 2 to the degree count of single vertex ) and Hence sum of degree of all the vertices is twice
the number of edges .
that is X
deg(v) = 2 · m
v∈V (G)

Hence Proved .
(c) Your next task is to deduce the following consequence of Lemma 0.1: [1]
Corollary 0.2. The number of vertices that have odd degree, in any graph, is even.
Response: Since we have proved above that sum of degrees of a graph is always even , hence
we can divide degree sequence into 2 sets , odd degrees (S1 ) and even degrees (S2). Now sum of
degrees of S2 will be even because sum of 2 even numbers is always even and for the total sum of
degrees from S1 and S2 to be even , sum of degrees from S1 should also be even ( otherwise even
+ odd = odd , which is contradiction ) .
P
Now For i∈S1 ı to be even we should be able to couple each and every number with some other
number of S1 which is possible iff number of elements in S1 is even .
Hence Number of vertices having odd degree must be even .

2. [Forests, Trees and Leaves] [14]

In lectures, we have proved the following (which is Theorem 2.1 in Bondy-Murty):

Lemma 0.3. If G is a (non-null) graph whose each vertex has degree at least two, then G contains a
cycle (as a subgraph).
Recall that a forest (also known as an acyclic graph) is a graph that does not contain any cycle (as a
subgraph). Convince yourself that Lemma 0.3 implies the following:

Corollary 0.4. Each (non-null) forest has a vertex of degree at most one. Furthermore, each nonempty
forest has a vertex of degree one.

A tree is any connected forest, and a leaf of a tree is any vertex of degree one.

(a) Your first task is to redraw the tree G2 shown in Figure 1, label its vertices, and indicate which
ones are leaves. [1.5]
v2 v5
v3 v6

v1 v4
G2
Response:
NOTE : Red circles denote the leaves .
(b) It follows from Corollary 0.4 that each tree, of order two or more, has at least one leaf. You next
task is to prove the following stronger statement: [4]
Lemma 0.5. Each tree, of order two or more, has at least two leaves.
Response:

Proof. Let P = v0 v1 · · · vk be a path of maximal length in T (i.e., P is not a proper subpath of any
other path in T ). We claim both endpoints of P are leaves.
Suppose, toward a contradiction, that deg(v0 ) ≥ 2. Then v0 has a neighbor u ̸= v1 . If u lies on P
but u ̸= v1 , then the edge uv0 together with the segment of P from u to v0 forms a cycle, which
is impossible in a tree. Hence u ∈ / {v1 , . . . , vk }, and then uv0 v1 · · · vk is a path longer than P ,
contradicting the maximality of P . Therefore deg(v0 ) = 1. The same argument applied to vk , so
deg(vk ) = 1. Thus T has at least two leaves.

(c) Your next task is to prove the following statement: [4]

Lemma 0.6. A vertex v of a tree T is a leaf if and only if T − v is a tree.
Response:

Proof. Claim : a vertex v is a leaf only if T-v is a Tree .

Suppose degT (v) = 1, say NT (v) = {u}. (Here NT (v) denotes neighbour of vertex v .) First, T − v
is acyclic because deleting vertices cannot create cycles. Next, we need to show T − v is connected.
Take any x, y ∈ V (T ) \ {v}. Let P be the unique x–y path in T . If P passes through v, then it
would enter v via uv and have to leave v along a second edge, contradicting degT (v) = 1. Hence v
can’t lie in P and lies entirely in T − v, so T − v is connected. Thus T − v is a connected acyclic
graph, i.e., a tree.

Claim : A vertex v is a leaf if T-v is a tree .

Suppose T − v is a tree . If degT (v) = 0 then T would have two components, T − v and {v},
contradicting that T is connected. If degT (v) ≥ 2, pick two distinct neighbors x ̸= y of v. Since
T − v must be connected, there is an x–y path P in T − v. Then P ∪ {vx, vy} is a cycle in T ,
contradicting that T is acyclic. Therefore degT (v) = 1, so v is a leaf.

(d) Your next task is to use some of the above results and induction to prove the following: [3]
Corollary 0.7. The size of any tree T is precisely one less than its order. In other words, m = n−1
for any tree T .
 Response: To Prove :- If T is a finite tree with n = |V (T )| vertices, then |E(T )| = n − 1.

Top–down induction. Fix an arbitrary tree T with n ≥ 1 vertices. Define the sequence of graphs

Tn := T, Tk−1 := Tk − vk (k = n, n − 1, . . . , 2),

where at each step vk is a leaf of Tk . Such a vertex exists in every tree(non empty) , and by the
lemma proved earlier,

vk is a leaf of Tk ⇐⇒ Tk−1 = Tk − vk is a tree.

Hence each Tk−1 is again a tree. Also, removing a leaf decreases both the number of vertices and
the number of edges by exactly 1; therefore the quantity

I(G) := |E(G)| − |V (G)|

is invariant along the chain Tn , Tn−1 , . . . , T1 :

I(Tk−1 ) = |E(Tk )| − 1 − |V (Tk )| − 1 = I(Tk ) for k = n, . . . , 2.

Consequently I(T ) = I(T1 ). But T1 is the one-vertex tree, so |E(T1 )| = 0 and |V (T1 )| = 1, hence
I(T1 ) = −1. Therefore
|E(T )| − |V (T )| = I(T ) = I(T1 ) = −1,
i.e. |E(T )| = |V (T )| − 1 = n − 1 as claimed.

(e) Your final task is to draw a graph G that satisfies m = n − 1 but is not a tree. [1.5]
v2 v5
v3 v6

v1 v4
Response: G

3. [Trees and their Degree Sequences] [10]

In this exercise, our goal is to characterize the degree sequences of trees.

(a) Given a sequence of positive integers (d1 , d2 , . . . , dn ) such that n ≥ 2 and ni=1 di = 2n − 2, your
P
first task is to prove the following two statements (that have nothing to do with graph theory): [3]
(i) There exists i ∈ {1, 2, . . . , n} such that di = 1.
Response:
Proof by contradiction. Assume, to the contrary, that di ̸= 1 for every i. Since each di is a
positive integer, this means di ≥ 2 for all i, hence
n
X
di ≥ 2n.
i=1
Pn
But by hypothesis i=1 di = 2n − 2, a contradiction. Therefore some di must equal 1.
(ii) If n ≥ 3 then there exists i ∈ {1, 2, . . . , n} such that di > 1.
Response:
 Proof by contradiction. Suppose not; then di ≤ 1 for all i. Since each di is a positive integer,
we must have di = 1 for all i, so
Xn
di = n.
i=1
Pn
Comparing with i=1 di = 2n − 2 gives n = 2n − 2, i.e., n = 2, which contradicts n ≥ 3.
Hence there exist some di satisfying di > 1.
(b) Your final task is to prove the following theorem that characterizes degree sequences of trees. [7]
Theorem 0.8. A sequence Pn of positive integers (d1 , d2 , . . . , dn ), where n ≥ 2, is a degree sequence
of a tree if and only if i=1 di = 2n − 2.
Hint: For one of the two implications, use induction and part (a).
Response: Let n ∈ N and let d1 , . . . , dn be integers. For n ≥ 2 the following are equivalent:
(i) There exists a tree T on n vertices whose degree sequence (up to order) is (d1 , . . . , dn ).
n
X
(ii) di ≥ 1 for all i and di = 2n − 2.
i=1

For n = 1, the unique tree has degree sequence (0).

P
Ambiguity
P remark. The condition i di = 2n − 2 does not imply that a given graph with those
n and di is a tree; the correct interpretation is that a sequence (di ) with that sum is realisable
as the degree sequence of some tree.

Proof. (i)⇒(ii): If T is a tree on n vertices then |E(T )| = n − 1. By the Handshake Lemma,

n
X X
di = degT (v) = 2|E(T )| = 2(n − 1) = 2n − 2,
i=1 v∈V (T )

and in a tree with n ≥ 2 every vertex has degree at least 1.

(ii)⇒(i): We argue by induction on n.
P
Base n = 2. From di = 2 and di ≥ 1, we get (d1 , d2 ) = (1, 1), realised by the single edge.
Let n ≥ 3 and suppose the claim holds for all smaller sizes. Given positive integers d1 , . . . , dn
Step. P
with di = 2n − 2, there exists an index a with da = 1 (proved above), and there exists an index
b with db ≥ 2 (proved above ). Form a sequence on n − 1 terms by deleting da and replacing db by
db − 1:
(d′1 , . . . , d′n−1 ) with {d′j } = {di : i ̸= a, b} ∪ {db − 1}.

Then each d′j ≥ 1 and

n−1 n
!
X X
d′j = di − 2 = 2(n − 1) − 2 = 2(n − 2).
j=1 i=1

By the induction hypothesis, there exists a tree T ′ on n − 1 vertices with degree sequence (d′j ).
Obtain T from T ′ by adding a new vertex va and joining it to the vertex corresponding to db −1. This
increases that vertex’s degree by 1 and makes deg(va ) = 1, so T has degree sequence (d1 , . . . , dn ).
Moreover, attaching a leaf to a tree yields a tree (proved above). Thus a tree with the required
degree sequence exists.
This completes the proof.