Tutorial 8 – Solution
1. Prove that the chromatic number of a graph will not exceed by more
than one the maximum degree of the vertices in a graph.
1. Chromatic Number ≤ Maximum Degree + 1
Theorem:
For any simple graph G, the chromatic number χ(G)≤Δ(G)+1,
where Δ(G) is the maximum degree of any vertex in G.
Proof (Greedy Coloring Algorithm):
• Consider an ordering of vertices v1,v2,…,vn.
• Assign colors to each vertex vi using the smallest available color not used by its
neighbors.
• Each vertex vi has at most Δ(G) neighbors, so at most Δ(G) colors may be unavailable.
• Therefore, we always have at least one of the Δ(G)+1 colors available.
Hence, χ(G)≤Δ(G)+1.
Proved.
2. Show that if a bipartite graph has any circuits, they must all be of
even lengths.
2. Circuits in Bipartite Graphs Are Even
Proof:
• In a bipartite graph, the vertex set is partitioned into two disjoint sets A and B, such that
every edge connects a vertex in A to a vertex in B.
• In a circuit, you alternate between vertices.
• Starting from A, next vertex is in B, then back to A, and so on.
• To return to the starting vertex (and close the cycle), we must have even number of steps.
So, all cycles in bipartite graphs are of even length.
3. G is a bipartite graph. Show that G has no cycle of ODD length.
3. Bipartite Graphs Have No Odd-Length Cycles
This is equivalent to the previous point.
Proof by Contrapositive:
• Suppose graph G has an odd-length cycle.
• Then it cannot be bipartite, because no partitioning avoids adjacent vertices ending up in
the same set.
• Hence, if G is bipartite, it must not contain any odd-length cycle.
Proved.
4. In a chessboard, show the positions of
a. The minimum number of queens that collectively dominate all
64 squares (an example of a minimal dominating with smallest
number of vertices).
b. The maximum number of queens such that none of them can
take another (an example of a maximal independent set with
largest number of vertices).
4. Queens on a Chessboard
(a) Minimum Dominating Set of Queens
• A queen dominates all squares in her row, column, and diagonals.
• It is known from combinatorics that the minimum number of queens to dominate the
entire 8×8 board is 5.
Example configuration (rows, columns):
• (1,1), (2,5), (4,8), (6,3), (8,7)
Each queen covers many squares; collectively, they cover all.
(b) Maximum Non-Attacking Queens
• This is the classic 8-Queens problem.
• Max number of queens that don’t attack each other is 8.
Example configuration (rows, columns):
• (1,1), (2,5), (3,8), (4,6), (5,3), (6,7), (7,2), (8,4)
Each queen is in a different row, column, and diagonal.
5. Find the chromatic polynomial of the following graphs:
6. Show that the chromatic polynomial of a graph consisting of a single circuit of length (i.e.,
an n-gon) is Pn(λ) = (λ − 1)n + (λ − 1)(λ − 1)n.
6. Chromatic Polynomial of a Cycle Cn
Let Cn be a cycle graph of n vertices.
The chromatic polynomial of a cycle of n vertices is:
P(Cn,λ)= (λ − 1)n + (λ − 1)(λ − 1)n
This formula arises due to inclusion-exclusion applied to coloring with adjacent vertex
constraints.
7. For a graph with n vertices and m edges if δ is the min degree and Δ Δ is max degree then
PT δ ≤ 2m/n ≤ Δ
