Problem Set 16
Online Math Club
October 3, 2024
Introduction
This problem set contains problems on Introduction to Graph theory compiled by
Nandagovind Anurag and Polynomials compiled by Kanav Talwar and Sanjana Philo
Chacko.
Instructions:
• You can discuss the problems with one another and come up with solutions together
as well. This is especially encouraged for harder problems. We would request you
to solve the easier ones independently.
• You are also encouraged to ask for hints on the server on problems you’re struggling
with.
• The solutions/sources of the problems will be posted with the next Pset.
• Problems are roughly ordered by difficulty.
• Enjoy the problems!
1
Online Math Club Problem Set 16
§1 Problems
Problem 1.1. Let G be a connected graph. An edge e is said to be a cut-edge if its
removal disonnects the graph. Prove that e is not a cut-edge if and only if e is an edge of
a cycle
Problem 1.2. Prove that a graph is bipartite if and only if it does not contain an odd
cycle.
Problem 1.3. Let G be a connected graph with an even number of vertices. Prove that
you can select a subset of edges of G such that each vertex is incident to an odd number
of selected edges
Problem 1.4. Let T be a tree of ordern ≥ 2. Prove that the number of leaves of T is
2 + Σd(u)≥3 (d(u) − 2)
Problem 1.5. Let ni denote number of elements with degree exactly i . Prove that the
above formula can be written as 2 + Σ∞
i=2 (i − 2)ni
Problem 1.6. Show that for a connected graph G, n1 = 2 + Σ∞
i=2 (i − 2)ni ⇐⇒ G is a
tree.
Problem 1.7. Find all polynomials with real coefficients such that xp(x3 ) = p(x2 )q(x2 ).
Problem 1.8. Find all polynomials with real coefficients P (x) such that P (x2 + x + 1)
divides P (x3 − 1).
Problem 1.9. Let A = A(x, y) and B = B(x, y) be two-variable polynomials with real
coefficients. Suppose that A(x, y)/B(x, y) is a polynomial in x for infinitely many values
of y, and a polynomial in y for infinitely many values of x. Prove that B divides A,
meaning there exists a third polynomial C with real coefficients such that A = B · C.
Problem 1.10. Suppose a0 , . . . , a100 are positive reals. Consider the following polynomial
for each k in {0, 1, . . . , 100}:
a100+k x100 + 100a99+k x99 + a98+k x98 + a97+k x97 + · · · + a2+k x2 + a1+k x + ak ,
where indices are taken modulo 101, i.e., a100+i = ai−1 for any i in {1, 2, . . . , 100}. Show
that it is impossible that each of these 101 polynomials has all its roots real.
2
Online Math Club Problem Set 16
§2 Bonus Problems
Problem 2.1. Let n be a positive even integer, and let c1 , c2 , . . . , cn−1 be real numbers
satisfying
n−1
X
|ci − 1| < 1.
i=1
Prove that
2xn − cn−1 xn−1 + cn−2 xn−2 − · · · − c1 x1 + 2
has no real roots.
Problem 2.2. Suppose f, g ∈ R[x] are non constant polynomials. Suppose neither of
f, g is the square of a real polynomial but f (g(x)) is. Prove that g(f (x)) is not the square
of a real polynomial.
Problem 2.3. Determine all monic polynomials having all real roots and each coefficient
as 1 or -1.
Problem 2.4. Find all pairs of positive integers m, n ≥ 3 such that the polynomial
xn + x2 − 1 divides the polynomial xm + x − 1
3
Online Math Club Problem Set 16
§3 Solutions/Sources to PSet 15
Problem 3.1.
Problem 3.2. Fermat
Problem 3.3. APMO 2017 P1
Problem 3.4. Observe that a|b =⇒ a2 |b =⇒ a3 |b · · ·
Problem 3.5. IMO 2007 P5
Problem 3.6.
Problem 3.7. Canada 2000
Problem 3.8. IGO 2017/E3
Problem 3.9. Canada 1977/4
Problem 3.10. ISL 2012 G1
Problem 3.11. ISL 2021 G1
Problem 3.12. IMO 1985/1
Problem 3.13. ISL 2015 G1
Problem 3.14. 2023 G3
§3.1 Solutions/Sources to Bonus problems
Problem 3.15. 2019 N8
Problem 3.16. Fermst’s theorem
Problem 3.17. China TST 2018
Problem 3.18. INMO 2021/5
Problem 3.19. ISL 2022 G3