Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2019: Graph Coloring

G
Topic
First Poster
Last Poster
Equivalence of two conjectures
notethanol   3
N Dec 9, 2019 by JGeneson
In Brimkov proposition 17, we are given that Conjecture 3 is true if and only if Conjecture 4 is true.

(Note that Conjecture 3 is the Line EFL Conjecture (or Conjecture A in the exercise): "Let M be a set of m lines drawn in the plane. Then, M has an EFL coloring with m colors")
(Also note that Conjecture 4 is the Segment EFL Conjecture (or Conjecture B in the exercise): "Let M be a set of m segments drawn in the plane. Then, M has an EFL coloring with m colors")

Thus, if Conjecture 3 is true, then Conjecture 4 is also true; if Conjecture 3 is false, then Conjecture 4 is also false. Since the 2 conjectures have the same truth values, it can be said that Conjectures 3 and 4 are equivalent.
3 replies
notethanol
Oct 19, 2019
JGeneson
Dec 9, 2019
No more topics!
a