Scribd
Upload
8 views1 page

Combinatorics and Graph Theory Problems

This document contains solutions to problems from a combinatorics and graph theory course. It first summarizes the problem statement for Problem 5 parts (a) and (b), which asks to prove properties about paths and cycles in graphs based on their minimum degree. It then provides detailed solutions to each part using proofs by contradiction. The document also summarizes and solves Problem 2 about relating the diameter and clique number of a graph.

Uploaded by

Sanjoy Pandit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views1 page

Combinatorics and Graph Theory Problems

This document contains solutions to problems from a combinatorics and graph theory course. It first summarizes the problem statement for Problem 5 parts (a) and (b), which asks to prove properties about paths and cycles in graphs based on their minimum degree. It then provides detailed solutions to each part using proofs by contradiction. The document also summarizes and solves Problem 2 about relating the diameter and clique number of a graph.

Uploaded by

Sanjoy Pandit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Math 368. Combinatorics and Graph Theory. Fall 2012.

List of problems:
Problem 5, page 9. Page 1.

Problem 5, page 9. Let G be a graph with δ(G) ≥ k.


(a) Prove that G has a path of length at least k.
(b) If k ≥ 2, prove that G has a cycle of length at least k + 1.

Solution to (a). For k = 0 the statement is trivial because for any v ∈ V the sequence v (of one term
in V ) forms a path of length 0.
So we assume that k ≥ 1. Let n be the maximal possible length of a path in G, and let v1 , v2 , . . . , vn+1
be such a path of length n. In order to prove (a), we have to show that n ≥ k.

If not (thus the proof is conducted by contradiction), then n < k. Denote S = N (vn+1 )\ vi | 1 ≤ i ≤ n .
We have |S| ≥ δ(G) − n ≥ k − n ≥ 1, i.e. S 6= ∅. Pick u ∈ S. Then the sequence v1 , v2 , . . . , vn+1 , u forms
a path of length n + 1, a contradiction with the assumption that n is the maximal length of a path in the
graph G.

Solution to (b). If δ(G) = 1, G does not need to have cycles (example: Pn , n ≥ 2).
Now assume that k ≥ 2. As in the previous proof, let n be the maximal possible length of a path in G,
and let v1 , v2 , . . . , vn+1 be such a path of length n. It follows from (a) that n ≥ k. Consider

S = N (vn+1 ) \ vi | n − k + 2 ≤ i ≤ n .
Clearly, |S| ≤ k − (k − 1) = 1, i.e., S 6= ∅. Pick u ∈ S. Then the walk v1 , v2 , . . . , vn+1 , u cannot be
a path because its length is n + 1 > n. It follows that u = vm , for some m ∈ [1, n − k + 1], and then
vm , vm+1 , . . . , vn+1 , u is a path of length n + 1 − m + 1 = n + 2 − m ≥ n + 2 − (n − k + 1) = k + 1, completing
the proof of (b).

Problem 2 (from Test 1). Prove that if diam(G) = 8 then ω(G) ≥ 5.


Solution. If diam(G) = 8, there are u, v ∈ V such that d(u, v) = 8. Then there exists an u_v-path
(1) u0 , u1 , . . . , u7 , u8
such that u0 = u and u8 = v.

Claim. For integers i, j such that 0 ≤ i ≤ j ≤ 8, d(ui , uj ) = j − i.


Proof #1 of the Claim.
This has been proved in class for any geodesic path. (A path u_v is geodesic if its length is equal to d(u, v)).
Proof #2 of the Claim. (Direct proof: If you do not remember the geodesic result).
Clearly, d(ui , uj ) ≤ j − i because the path (1) contains a path between ui and uj of length j − i.
Now assume to the contrary that d(ui , uj ) < j − i. Then by the triangle inequality
d(u, v) = d(u0 , u8 ) ≤ d(u0 , ui ) + d(ui , uj ) + d(uj , u8 ) ≤ i + d(ui , uj ) + (8 − j) =
(2) = 8 + i − j + d(ui , uj ) < 8 + i − j + (j − i) = 8,
a contradiction with the choice of u, v such that d(u, v) = 8.
It folows from (2) that the distances between any two different vertices in the set
W = {u0 , u2 , u4 , u6 , u8 }
is at least 2, hence every pair in the set W lies in E(G). ω(G) ≥ 5. Since |W | = 5, it follows that ω(G) ≥ 5.
The students who instead of writing down explicitly (2) just pointed out that all distances in the set W
exceed 2 because otherwise by the triangle inequality d(u, v) < 8 received full credit.

You might also like