ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.06
https://doi.org/10.26493/1855-3974.3233.185
(Also available at http://amc-journal.eu)
Distinguishing colorings, proper colorings, and
covering properties without AC*
Amitayu Banerjee †
Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053, Budapest, Hungary
Zalán Molnár ‡ , Alexa Gopaulsingh
Eötvös Loránd University, Department of Logic, Múzeum krt. 4, 1088, Budapest, Hungary
Received 24 September 2023, accepted 20 March 2024, published online 26 September 2024
Abstract
We work with simple graphs in ZF (i.e., the Zermelo–Fraenkel set theory without the
Axiom of Choice (AC)) and assume that the sets of colors can be either well-orderable
or non-well-orderable, to prove that the following statements are equivalent to Kőnig’s
Lemma:
(a) Any infinite locally finite connected graph G such that the minimum degree of G is
greater than k, has a chromatic number for any fixed integer k greater than or equal
to 2.
(b) Any infinite locally finite connected graph has a chromatic index.
(c) Any infinite locally finite connected graph has a distinguishing number.
(d) Any infinite locally finite connected graph has a distinguishing index.
The above results strengthen some recent results of Stawiski since he assumed that the sets
of colors can be well-ordered. We formulate new conditions for the existence of irreducible
proper coloring, minimal edge cover, maximal matching, and minimal dominating set in
connected bipartite graphs and locally finite connected graphs, which are either equivalent
to AC or Kőnig’s Lemma. Moreover, we show that if the Axiom of Choice for families of
2-element sets holds, then the Shelah-Soifer graph has a minimal dominating set.
*The authors are very thankful to the three anonymous referees for reading the manuscript in detail and for
providing several comments and suggestions that improved the quality and the exposition of the paper.
†Corresponding author.
‡Supported by the ÚNKP-23-3 New National Excellence Program of the Ministry of Culture and Innovation
from the source of the national research, development and innovation fund.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P4.06
Keywords: Axiom of Choice, proper colorings, distinguishing colorings, minimal edge cover, maximal
matching, minimal dominating set.
Math. Subj. Class. (2020): Primary 03E25; Secondary 05C63, 05C15, 05C69
1 Introduction
In 1991, Galvin–Komjáth proved that the statements “Any graph has a chromatic num-
ber” and “Any graph has an irreducible proper coloring” are equivalent to AC in ZF using
Hartogs’s theorem (cf. [7]). In 1977, Babai [1] introduced distinguishing vertex colorings
under the name asymmetric colorings, and distinguishing edge colorings were introduced
by Kalinowski–Pilśniak [14] in 2015. Recently, Stawiski [20] proved that the statements
(b)–(d) mentioned in the abstract above and the statement “Any infinite locally finite con-
nected graph has a chromatic number” are equivalent to Kőnig’s Lemma (a weak form
of AC) by assuming that the sets of colors can be well-ordered (cf. [20, Lemma 3.3 and
Section 2]).
1.1 Proper and distinguishing colorings
An infinite cardinal in ZF can either be an ordinal or a set that is not well-orderable.
Herrlich–Tachtsis [10, Proposition 23] proved that no Russell graph has a chromatic num-
ber in ZF. We refer the reader to [10] for the details concerning Russell graph and Russell
sequence. In Theorem 4.2, the first and the second authors study new combinatorial proofs
(mainly inspired by the arguments of [10, Proposition 23]) to show that the statements (a)–
(d) mentioned in the abstract above are equivalent to Kőnig’s Lemma (without assuming
that the sets of colors can be well-ordered).1
1.2 New equivalents of Kőnig’s lemma and AC
The role of AC and Kőnig’s Lemma in the existence of graph-theoretic properties like ir-
reducible proper coloring, chromatic numbers, maximal independent sets, spanning trees,
and distinguishing colorings were studied by several authors in the past (cf. [2, 3, 5, 6, 7,
11, 19, 20]). We list a few known results apart from the above-mentioned results due to
Galvin–Komjáth [7] and Stawiski [20]. In particular, Friedman [6, Theorem 6.3.2, Theo-
rem 2.4] proved that AC is equivalent to the statement “Any graph has a maximal indepen-
dent set”. Höft–Howard [11] proved that the statement “Any connected graph contains a
partial subgraph which is a tree” is equivalent to AC. Fix any even integer m ≥ 4 and any
integer n ≥ 2. Delhommé–Morillon [5] studied the role of AC in the existence of span-
ning subgraphs and observed that AC is equivalent to “Any connected bipartite graph has a
spanning subgraph without a complete bipartite subgraphKn,n” as well as “Any connected
graph admits a spanning m-bush” (cf. [5, Corollary 1, Remark 1]). They also proved that
the statement “Any locally finite connected graph has a spanning tree” is equivalent to
Kőnig’s lemma in [5, Theorem 2]. Banerjee [2, 3] observed that the statements “Any infi-
E-mail addresses: banerjee.amitayu@gmail.com (Amitayu Banerjee), mozaag@gmail.com (Zalán Molnár),
alexa279e@gmail.com (Alexa Gopaulsingh)
1We note that statement (a) mentioned in the abstract is a new equivalent of Kőnig’s Lemma. Stawiski’s graph
from [20, Theorem 3.6] shows that Kőnig’s Lemma is equivalent to “Every infinite locally finite connected graph
G such that δ(G) (the minimum degree of G) is 2 has a chromatic number”.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 3
nite locally finite connected graph has a maximal independent set” and “Any infinite locally
finite connected graph has a spanningm-bush” are equivalent to Kőnig’s lemma. However,
the existence of maximal matching, minimal edge cover, and minimal dominating set in ZF
were not previously investigated. The following table summarizes the new results (cf. The-
orem 5.1, Theorem 6.4).2
New equivalents of Kőnig’s lemma New equivalents of AC
Plf,c(irreducible proper coloring)
Plf,c(minimal dominating set) Pc(minimal dominating set)
Plf,c(maximal matching) Pc,b(maximal matching)
Plf,c(minimal edge cover) Pc,b(minimal edge cover)
In the table, Plf,c(property X) denotes “Any infinite locally finite connected graph has
property X”, Pc,b(property X) denotes “Any connected bipartite graph has property X”
and Pc(property X) denotes “Any connected graph has property X”.
2 Basics
Definition 2.1. Suppose X and Y are two sets. We write:
1. X  Y , if there is an injection f : X → Y .
2. X and Y are equipotent ifX  Y and Y  X , i.e., if there is a bijection f : X → Y .
3. X ≺ Y , if X  Y and X is not equipotent with Y .
Definition 2.2. Without AC, a set m is called a cardinal if it is the cardinality |x| of some
set x, where |x| = {y : y ∼ x and y is of least rank} where y ∼ x means the existence of a
bijection f : y → x (see [15, Definition 2.2, page 83] and [13, Section 11.2]).
Definition 2.3. A graph G = (VG, EG) consists of a set VG of vertices and a set EG ⊆
[VG]
2 of edges.3 Two vertices x, y ∈ VG are adjacent vertices if {x, y} ∈ EG, and two
edges e, f ∈ EG are adjacent edges if they share a common vertex. The degree of a vertex
v ∈ VG, denoted by deg(v), is the number of edges emerging from v. We denote by δ(G)
the minimum degree ofG. Given a non-negative integer n, a path of length n inG is a one-
to-one finite sequence {xi}0≤i≤n of vertices such that for each i < n, {xi, xi+1} ∈ EG;
such a path joins x0 to xn.
(1) G is locally finite if every vertex of G has a finite degree.
(2) G is connected if any two vertices are joined by a path of finite length.
(3) A dominating set of G is a set D of vertices of G, such that any vertex of G is either
in D, or has a neighbor in D.
(4) An independent set of G is a set of vertices of G, no two of which are adjacent
vertices. A dependent set of G is a set of vertices of G that is not an independent set.
2We note that Theorem 5.1 is a combined effort of the first and the second authors. Moreover, all remarks in
Section 6 including Theorem 6.4 are due to all the authors.
3i.e., EG is a subset of the set of all two-element subsets of VG.
4 Ars Math. Contemp. 24 (2024) #P4.06
(5) A vertex cover of G is a set of vertices of G that includes at least one endpoint of
every edge of the graph G.
(6) A matching M in G is a set of pairwise non-adjacent edges.
(7) An edge cover of G is a set C of edges such that each vertex in G is incident with at
least one edge in C.
(8) A minimal dominating set (minimal vertex cover, minimal edge cover) is a dominat-
ing set (a vertex cover, an edge cover) that is not a superset of any other dominating
set (vertex cover, edge cover). A maximal independent set (maximal matching) is
an independent set (a matching) that is not a subset of any other independent set
(matching).
(9) A proper vertex coloring of G with a color set C is a mapping f : VG → C such
that for every {x, y} ∈ EG, f(x) 6= f(y). A proper edge coloring of G with a color
set C is a mapping f : EG → C such that for any two adjacent edges e1 and e2,
f(e1) 6= f(e2).
(10) Let |C| = κ. We say G is κ-proper vertex colorable or C-proper vertex colorable if
there is a proper vertex coloring f : VG → C and G is κ-proper edge colorable or
C-proper edge colorable if there is a proper edge coloring f : EG → C. The least
cardinal κ for which G is κ-proper vertex colorable (if it exists) is the chromatic
number of G and the least cardinal κ for which G is κ-proper edge colorable (if it
exists) is the chromatic index of G.
(11) A proper vertex coloring f : VG → C is aC-irreducible proper coloring if f−1(c1)∪
f−1(c2) is a dependent set whenever c1, c2 ∈ C and c1 6= c2 (cf. [7]).
(12) An automorphism ofG is a bijection φ : VG → VG such that {u, v} ∈ EG if and only
if {φ(u), φ(v)} ∈ EG. Let f be an assignment of colors to either vertices or edges of
G. We say that an automorphism φ ofG preserves f if each vertex ofG is mapped to
a vertex of the same color or each edge of G is mapped to an edge of the same color.
We say that f is a distinguishing coloring if the only automorphism that preserves
f is the identity. Let |C| = κ. We say G is κ-distinguishing vertex colorable or C-
distinguishing vertex colorable if there is a distinguishing vertex coloring f : VG →
C and G is κ-distinguishing edge colorable or C-distinguishing edge colorable if
there is a distinguishing edge coloring f : EG → C. The least cardinal κ for which
G is κ-distinguishing vertex colorable (if it exists) is the distinguishing number of G
and the least cardinal κ for which G is κ-distinguishing edge colorable (if it exists)
is the distinguishing index of G.
(13) The automorphism group of G, denoted by Aut(G), is the group consisting of auto-
morphisms of G with composition as the operation. Let τ be a group acting on a set
S and let a ∈ S. The orbit of a, denoted by Orbτ (a), is the set {φ(a) : φ ∈ τ}.
(14) G is complete if each pair of vertices is connected by an edge. We denote by Kn, the
complete graph on n vertices for any natural number n ≥ 1.
(15) Kőnig’s Lemma states that every infinite locally finite connected graph has a ray.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 5
Let ω be the set of natural numbers, Z be the set of integers, Q be the set of rational
numbers, R be the set of real numbers, and Q+a = {a+r : r ∈ Q} for any a ∈ R. Shelah–
Soifer [17] constructed a graph whose chromatic number is 2 in ZFC and uncountable in
some model of ZF (e.g. in Solovay’s model from [18, Theorem 1]).
Definition 2.4 (cf. [17]). The Shelah–Soifer Graph G = (R, ρ) is defined by xρy ⇔
(x− y) ∈ (Q+
√
2) ∪ (Q+ (−
√
2)).
Definition 2.5. A setX is Dedekind-finite if it satisfies the following equivalent conditions
(cf. [10, Definition 1]):
• ω 6 X ,4
• A ≺ X for every proper subset A of X .
Definition 2.6. For every family B = {Bi : i ∈ I} of non-empty sets, B is said to have a
partial choice function if B has an infinite subfamily C with a choice function.
Definition 2.7 (A list of choice forms).
(1) AC2: Every family of 2-element sets has a choice function.
(2) ACfin: Every family of non-empty finite sets has a choice function.
(3) ACωfin: Every countably infinite family of non-empty finite sets has a choice function.
We recall that ACωfin is equivalent to Kőnig’s Lemma as well as the statement “The
union of a countable family of finite sets is countable”.
(4) ACωk×fin for k ∈ ω\{0, 1}: Every countably infinite family A = {Ai : i ∈ ω} of
non-empty finite sets, where k divides |Ai|, has a choice function.
(5) PACωk×fin for k ∈ ω\{0, 1}: Every countably infinite family A = {Ai : i ∈ ω} of
non-empty finite sets, where k divides |Ai| has a partial choice function.
Definition 2.8. From the point of view of model theory, the language of graphs L consists
of a single binary relational symbol E depicting edges, i.e., L = {E} and a graph is an
L-structure G = 〈V,E〉 consisting of a non-empty set V of vertices and the edge relation
E on V . Let G = 〈V,E〉 be an L-structure, φ(x1, ..., xn) be a first-order L-formula, and
let a1, ..., an ∈ V for some n ∈ ω\{0}. We write G |= φ(a1, ..., an), if the property
expressed by φ is true in G for a1, ..., an. Let G1 = 〈VG1 , EG1〉 and G2 = 〈VG2 , EG2〉
be two L-structures. We recall that if j : VG1 → VG2 is an isomorphism, ϕ(x1, ..., xr) is a
first-order L-formula on r variables for some r ∈ ω\{0}, and ai ∈ VG1 for each 1 ≤ i ≤ r,
then by induction on the complexity of formulae, one can see that G1 |= ϕ(a1, ..., ar) if
and only if G2 |= ϕ(j(a1), ..., j(ar)) (cf. [16, Theorem 1.1.10]).
3 Known and basic results
3.1 Known results
Fact 3.1 (ZF). The following hold:
4i.e., there is no injection f : ω → X .
6 Ars Math. Contemp. 24 (2024) #P4.06
(1) (Galvin–Komjáth; cf. [7, Lemma 3 and the proof of Lemma 2]). Any graph based
on a well-ordered set of vertices has an irreducible proper coloring and a chromatic
number.
(2) (Delhommé–Morillon; cf. [5, Lemma 1]). Given a set X and a set A which is the
range of no mapping with domain X , consider a mapping f : A→ P(X)\{∅} (with
values non-empty subsets of X). Then there are distinct a and b in A such that
f(a) ∩ f(b) 6= ∅.
(3) (Herrlich–Rhineghost; cf. [9, Theorem]). For any measurable subset X of R with a
positive measure there exist x ∈ X and y ∈ X with y − x ∈ Q+
√
2.
(4) (Stawiski; cf. [20, proof of Theorem 3.8]). Any graph based on a well-ordered set of
vertices has a chromatic index, a distinguishing number, and a distinguishing index.
3.2 Basic results
Proposition 3.2 (ZF). The Shelah-Soifer Graph G = (R, ρ) has the following properties:
(1) If AC2 holds, then G has a minimal dominating set.
(2) Any independent set of G is either non-measurable or of measure zero.
Proof. First, we note that each component of G is infinite, since x, y ∈ R are connected if
and only if x− y = q +
√
2z for some q ∈ Q and z ∈ Z, and G has no odd cycles.
(1). Under AC2, G has a 2-proper vertex coloring f : VG → 2 (see [9]). This is
because, since G has no odd cycles, each component of G has precisely two 2-proper
vertex colorings. Using AC2 one can select a 2-proper vertex coloring for each component,
in order to obtain a 2-proper vertex coloring of G. We claim that f−1(i) (which is an
independent set ofG) is a maximal independent set (and hence a minimal dominating set) of
G for any i ∈ {0, 1}. Fix i ∈ {0, 1} and assume that f−1(i) is not a maximal independent
set. Then f−1(i)∪{v} is an independent set for some v ∈ R\f−1(i) = f−1(1− i) and so
{v, x} 6∈ ρ for any x ∈ f−1(i). Since f−1(1− i) is an independent set, {v, x} 6∈ ρ for any
x ∈ f−1(1− i). This contradicts the fact that G has no isolated vertices.
(2). Let M be an independent set of G. Pick any x, y ∈M such that x 6= y. Then,
¬(yρx) =⇒ (y−x) 6∈ (Q+
√
2)∪(Q+(−
√
2)) = {r+
√
2 : r ∈ Q}∪{r−
√
2 : r ∈ Q}.
Thus, there are no x, y ∈ M where x 6= y such that y − x ∈ Q+
√
2. By Fact 3.1(3),
M is not a measurable set of R with a positive measure.
Proposition 3.3 (ZF). The following hold:
(1) Any graph based on a well-ordered set of vertices has a minimal vertex cover.
(2) Any graph based on a well-ordered set of vertices has a minimal dominating set.
(3) Any graph based on a well-ordered set of vertices has a maximal matching.
(4) Any graph based on a well-ordered set of vertices with no isolated vertex, has a
minimal edge cover.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 7
Proof. (1). Let G = (VG, EG) be a graph based on a well-ordered set of vertices and let
< be a well-ordering of VG. We use transfinite recursion, without invoking any form of
choice, to construct a minimal vertex cover. Let M0 = VG. Clearly, M0 is a vertex cover.
Assume that M0 is not a minimal vertex cover. Now, assume that for some ordinal number
αwe have constructed a sequence (Mβ)β<α of vertex covers such thatMβ is not a minimal
vertex cover for any β < α. If α = γ + 1 is a successor ordinal for some ordinal γ, then
let Mα = Mγ+1 = Mγ\{vγ} where vγ is the <-minimal element of the well-ordered set
{v ∈ Mγ : Mγ\{v} is a vertex cover}. If α is a limit ordinal, we use Mα =
⋂
β∈αMβ .
For any ordinal α, if Mα is a minimal vertex cover, then we are done. Since the class of
all ordinal numbers is a proper class, it follows that the recursion must terminate at some
ordinal stage, say λ. Then, Mλ is the minimal vertex cover.
(2). This follows from (1) and the fact that if I is a minimal vertex cover of G, then
VG\I is a maximal independent set (and hence a minimal dominating set) of G.
(3). If VG is well-orderable, then EG ⊆ [VG]2 is well-orderable as well. Thus, similar
to the arguments of (1) we can obtain a maximal matching by using transfinite recursion in
ZF and modifying the greedy algorithm to construct a maximal matching.
(4). Let G = (VG, EG) be a graph on a well-ordered set of vertices without isolated
vertices. Let≺′ be a well-ordering ofEG. By (3), we can obtain a maximal matchingM in
G. Let W be the set of vertices not covered by M . For each vertex w ∈ W , the set Ew =
{e ∈ EG : e is incident with w} is well-orderable being a subset of the well-orderable set
(EG,≺′). Let fw be the (≺′ Ew)-minimal element of Ew. Let F = {fw : w ∈ W} and
let M1 = {e ∈ M : at least one endpoint of e is not covered by F}. Then F ∪M1 is a
minimal edge cover of G.
Remark 3.4. We remark that the direct proofs of items (1)–(3) of Proposition 3.3 do not
adapt immediately to give a proof of item (4); the issue is in the limit steps, where a vertex
of infinite degree might not be covered anymore by the intersection of edge covers.
4 Proper and distinguishing colorings
Definition 4.1. Let A = {An : n ∈ ω} be a disjoint countably infinite family of non-
empty finite sets and T = {tn : n ∈ ω} be a countably infinite sequence disjoint from A =⋃
n∈ω An. Let G1(A, T ) = (VG1(A,T ), EG1(A,T )) be the infinite locally finite connected
graph such that
VG1(A,T ) := (
⋃
n∈ω
An) ∪ T,
EG1(A,T ) :=
{
{tn, tn+1} : n ∈ ω
}
∪
{
{tn, x} : n ∈ ω, x ∈ An
}
∪
{
{x, y} : n ∈ ω, x, y ∈ An, x 6= y
}
.
We denote by C the statement “For any disjoint countably infinite family of non-empty
finite sets A, and any countably infinite sequence T = {tn : n ∈ ω} disjoint from A =⋃
n∈ω An, the graphG1(A, T ) has a chromatic number” and we denote by Ck the statement
“Any infinite locally finite connected graphG such that δ(G) ≥ k has a chromatic number”.
Theorem 4.2 (ZF). Fix a natural number k ≥ 3. The following statements are equivalent:
(1) Kőnig’s Lemma.
8 Ars Math. Contemp. 24 (2024) #P4.06
(2) C.
(3) Ck.
(4) Any infinite locally finite connected graph has a chromatic number.
(5) Any infinite locally finite connected graph has a chromatic index.
(6) Any infinite locally finite connected graph has a distinguishing number.
(7) Any infinite locally finite connected graph has a distinguishing index.
Proof. (1)⇒(2)–(7) Let G = (VG, EG) be an infinite locally finite connected graph. Pick
some r ∈ VG. Let V0(r) = {r}. For each integer n ≥ 1, define Vn(r) = {v ∈ VG :
dG(r, v) = n} where “dG(r, v) = n” means there are n edges in the shortest path joining
r and v. Each Vn(r) is finite by the local finiteness of G, and VG =
⋃
n∈ω Vn(r) since G
is connected. By ACωfin, VG is countably infinite (and hence, well-orderable). The rest fol-
lows from Fact 3.1(1), (4) and the fact that G1(A, T ) is an infinite locally finite connected
graph for any given disjoint countably infinite family A of non-empty finite sets and any
countably infinite sequence T = {tn : n ∈ ω} disjoint from A =
⋃
n∈ω An.
(2)⇒(1) Since ACωfin is equivalent to its partial version PACωfin (Every countably infinite
family of non-empty finite sets has an infinite subfamily with a choice function) (cf. [12],
[4, the proof of Theorem 4.1(i)] or footnote 5), it suffices to show that C implies PACωfin. In
order to achieve this, we modify the arguments of Herrlich–Tachtsis [10, Proposition 23]
suitably. LetA = {An : n ∈ ω} be a countably infinite set of non-empty finite sets without
a partial choice function. Without loss of generality, we assume that A is disjoint. Pick a
countably infinite sequence T = {tn : n ∈ ω} disjoint from A =
⋃
i∈ω Ai and consider
the graph G1(A, T ) = (VG1(A,T ), EG1(A,T )) as in Figure 1.
• • • ...
A0
•
t0
• • • ...
A1
•
t1
...
...
Figure 1: Graph G1(A, T ), an infinite locally finite connected graph.
Let f : VG1(A,T ) → C be a C-proper vertex coloring of G1(A, T ), i.e., a map such
that if {x, y} ∈ EG1(A,T ) then f(x) 6= f(y). Then for each c ∈ C, the set Mc = {v ∈
f−1(c) : v ∈ Ai for some i ∈ ω} must be finite, otherwise Mc will generate a partial
choice function for A.
Claim 4.3. f [
⋃
n∈ω An] is infinite.
Proof. Otherwise,
⋃
n∈ω An =
⋃
c∈f [
⋃
n∈ω An]
Mc is finite since the finite union of finite
sets is finite in ZF and we obtain a contradiction.
Claim 4.4. f [
⋃
n∈ω An] is Dedekind-finite.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 9
Proof. First, we note that
⋃
n∈ω An is Dedekind-finite since A has no partial choice func-
tion. For the sake of contradiction, assume that C = {ci : i ∈ ω} is a countably infinite
subset of f [
⋃
n∈ω An]. Fix a well-ordering < of A (since A is countable, and hence well-
orderable). Define di to be the unique element of Mci ∩An where n is the <-least element
of {m ∈ ω :Mci ∩Am 6= ∅}. Such an n exists since ci ∈ f [
⋃
n<ω An] andMci ∩An has a
single element since f is a proper vertex coloring. Then {di : i ∈ ω} is a countably infinite
subset of
⋃
n∈ω An which contradicts the fact that
⋃
n∈ω An is Dedekind-finite.
The following claim states that C fails.
Claim 4.5. There is a C1-proper vertex coloring f : VG1(A,T ) → C1 of G1(A, T ) such
that C1 ≺ C. Thus, G1(A, T ) has no chromatic number.
Proof. Fix some c0 ∈ f [
⋃
n∈ω An]. Then Index(Mc0) = {n ∈ ω : Mc0 ∩ An 6= ∅} is
finite. By Claim 4.3, there exists some b0 ∈ (f [
⋃
n∈ω An]\
⋃
m∈Index(Mc0 )
f [Am]) since
the finite union of finite sets is finite. Define a proper vertex coloring g :
⋃
n∈ω An →
(f [
⋃
n∈ω An]\c0) as follows:
g(x) =
{
f(x) if f(x) 6= c0,
b0 otherwise.
Similarly, define a proper vertex coloring h :
⋃
n∈ω An → (f [
⋃
n∈ω An]\{c0, c1, c2})
for some c0, c1, c2 ∈ f [
⋃
n∈ω An]. Let h(t2n) = c0 and h(t2n+1) = c1 for all n ∈ ω.
Thus, h : VG1 → (f [
⋃
n∈ω An]\{c2}) is a f [
⋃
n∈ω An]\{c2}-proper vertex coloring of
G1. We define C1 = f [
⋃
n∈ω An]\{c2}. By Claim 4.4, C1 ≺ f [
⋃
n∈ω An]  C.
Similarly, we can see (4)⇒(1).
(3)⇒(1) Let A = {An : n ∈ ω} be a disjoint countably infinite set of non-empty
finite sets without a partial choice function, such that k divides |An| for each n ∈ ω and
k ∈ ω\{0, 1}. Assume T and G1(A, T ) as in the proof of (2)⇒(1). Then δ(G1(A, T )) ≥
k. By the arguments of (2)⇒(1), C implies PACωk×fin. Following the arguments of [4,
Theorem 4.1], we can see that PACωk×fin implies AC
ω
fin.
5
(5)⇒(1) Let A = {An : n ∈ ω} be a disjoint countably infinite set of non-empty finite
sets without a partial choice function and T = {tn : n ∈ ω} be a sequence disjoint from
A =
⋃
n∈ω An. Let H1 be the graph obtained from the graph G1(A, T ) of (2)⇒(1) after
deleting the edge set {{x, y} : n ∈ ω, x, y ∈ An, x 6= y}. Clearly, H1 is an infinite locally
finite connected graph.
Claim 4.6. H1 has no chromatic index.
5For the reader’s convenience, we write down the proof. First, we can see that PACωk×fin implies AC
ω
k×fin.
Fix a family A = {Ai : i ∈ ω} of disjoint nonempty finite sets such that k divides |Ai| for each i ∈ ω. Then
the family
B = {Bi : i ∈ ω} where Bi =
∏
j≤i Aj
is a disjoint family such that k divides |Bi| and any partial choice function on B yields a choice function forA.
Finally, fix a family C = {Ci : i ∈ ω} of disjoint nonempty finite sets. Then D = {Di : i ∈ ω} where
Di = Ci × k is a pairwise disjoint family of finite sets where k divides |Di| for each i ∈ ω. Thus ACωk×fin
implies that D has a choice function f which determines a choice function for C.
10 Ars Math. Contemp. 24 (2024) #P4.06
Proof. Assume that the graph H1 has a chromatic index. Let f : EH1 → C be a proper
edge coloring with |C| = κ, where κ is the chromatic index ofH1. LetB = {{tn, x} : n ∈
ω, x ∈ An}. Similar to Claims 4.3, 4.4, and 4.5, f [B] is an infinite, Dedekind-finite set
and there is a proper edge coloring h : B → f [B] \ {c0, c1, c2} for some c0, c1, c2 ∈ f [B].
Finally, define h({t2n, t2n+1}) = c0 and h({t2n+1, t2n+2}) = c1 for all n ∈ ω. Thus, we
obtain a f [B] \ {c2}-proper edge coloring h : EH1 → f [B] \ {c2}, with f [B] \ {c2} ≺
f [B]  C as f [B] is Dedekind-finite, contradicting the fact that κ is the chromatic index
of H1.
(6)⇒(1) Assume A and T as in the proof of (5)⇒(1). Let H11 be the graph obtained
fromH1 of (5)⇒(1) by adding two new vertices t′ and t′′ and the edges {t′′, t′} and {t′, t0}
(see Figure 2).
• • • ...
A0
•
t0
• • • ...
A1
•
t1
...
...
•
t′
•
t′′
Figure 2: Graph H11 , an infinite locally finite connected graph.
It suffices to show that H11 has no distinguishing number. We recall that whenever
j : VH11 → VH11 is an automorphism, ϕ(x1, ..., xr) is a first-order L-formula on r variables
(where L is the language of graphs) for some r ∈ ω\{0} and ai ∈ VH11 for each 1 ≤ i ≤ r,
then H11 |= ϕ(a1, ..., ar) if and only if H11 |= ϕ(j(a1), ..., j(ar)) (cf. Definition 2.8).
Claim 4.7. t′, t′′, and tm are fixed by any automorphism for each non-negative integer m.
Proof. Fix non-negative integers n,m, r. The first-order L-formula
Degn(x) := ∃x0. . .∃xn−1
( n−1∧
i 6=j
xi 6= xj∧
∧
i<n
x 6= xi∧
∧
i<n
Exxi∧∀y(Exy→
∨
i<n
y=xi)
)
expresses the property that a vertex x has degree n, where Eab denotes the existence of an
edge between vertices a and b. We define the following first-order L-formula:
ϕ(x) := Deg1(x) ∧ ∃y(Exy ∧ Deg2(y)).
It is easy to see the following:
(i) t′′ is the unique vertex such that H11 |= ϕ(t′′). This means t′′ is the unique vertex
such that deg(t′′) = 1 and t′′ has a neighbor of degree 2.
(ii) t′ is the unique vertex such that H11 |= Deg2(t′). So t′ is the unique vertex with
deg(t′) = 2.
Fix any automorphism τ . Since every automorphism preserves the properties mentioned in
(i)–(ii), t′ and t′′ are fixed by τ . The vertices tm are fixed by τ by induction as follows:
Since ti is the unique vertex of path length i+1 from t′′ such that the degree of ti is greater
than 1, where i ∈ {0, 1}, we have that t0 and t1 are fixed by τ . Assume that τ(tl) = tl for
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 11
all l < m− 1. We show that τ(tm) = tm. Now, τ(tm) is a neighbour of τ(tm−1) = tm−1
which is of degree at least 2, so τ(tm) must be either tm−2 or tm, but tm−2 = τ(tm−2) is
already taken. So, τ(tm) = tm.
Claim 4.8. Fixm ∈ ω and x ∈ Am. Then OrbAut(H11 )(x) = {g(x) :g∈Aut(H
1
1 )} = Am.
Proof. This follows from the fact that each y ∈
⋃
n∈ω An has path length 1 from tm if and
only if y ∈ Am.
Claim 4.9. H11 has no distinguishing number.
Proof. Assume that the graph H11 has a distinguishing number. Let f : VH11 → C be a
distinguishing vertex coloring with |C| = κ, where κ is the distinguishing number of H11 .
Similar to Claims 4.3 and 4.4, f [
⋃
n∈ω An] is infinite and Dedekind-finite. Consider a col-
oring h :
⋃
n∈ω An → f [
⋃
n∈ω An]\{c0, c1, c2} for some c0, c1, c2 ∈ f [
⋃
n∈ω An], just as
in Claim 4.5. Let h(t) = c0 for all t ∈ {t′′, t′}∪T . Then, h : VH11 → (f [
⋃
n∈ω An]\{c1, c2})
is a f [
⋃
n∈ω An] \ {c1, c2}-distinguishing vertex coloring of H11 . Finally, f [
⋃
n∈ω An] \
{c1, c2} ≺ f [
⋃
n∈ω An]  C contradicts the fact that κ is the distinguishing number of
H11 .
(7)⇒(1) Assume A, T , and H11 as in the proof of (6)⇒(1). By Claim 4.7, every auto-
morphism fixes the edges {t′′, t′}, {t′, t0} and {tn, tn+1} for each n ∈ ω. Moreover, if H11
has a distinguishing edge coloring f , then for each n ∈ ω and x, y ∈ An such that x 6= y,
f({tn, x}) 6= f({tn, y}).
Claim 4.10. H11 has no distinguishing index.
Proof. This follows modifying the arguments of Claims 4.6 and 4.9.
5 Irreducible proper coloring and covering properties
Theorem 5.1 (ZF). The following statements are equivalent:
(1) Kőnig’s Lemma.
(2) Every infinite locally finite connected graph has an irreducible proper coloring.
(3) Every infinite locally finite connected graph has a minimal dominating set.
(4) Every infinite locally finite connected graph has a minimal edge cover.
(5) Every infinite locally finite connected graph has a maximal matching.
Proof. Implications (1)⇒(2)–(5) follow from Proposition 3.3, and the fact that ACωfin im-
plies every infinite locally finite connected graph is countably infinite.
(2)⇒(1) In view of the proof of Theorem 4.2((2)⇒(1)), it suffices to show that the given
statement implies PACωfin. Let A = {An : n ∈ ω\{0}} be a disjoint countably infinite set
of non-empty finite sets without a partial choice function. Pick t 6∈
⋃
i∈ω\{0}Ai. Let
12 Ars Math. Contemp. 24 (2024) #P4.06
A0 = {t}. Consider the following infinite locally finite connected graph G2 = (VG2 , EG2)
(see Figure 3):
VG2 :=
⋃
n∈ω
An,
EG2 :=
{
{t, x} : x ∈ A1
}
∪
{
{x, y} : n ∈ ω\{0}, x, y ∈ An, x 6= y
}
∪
{
{x, y} : n ∈ ω\{0}, x ∈ An, y ∈ An+1
}
.
•t
•
•
•
A1 •
•
A2 •
•
•
A3 •
•
•
A4
...
Figure 3: The graph G2 when |A1| = |A3| = |A4| = 3, and |A2| = 2.
Claim 5.2. G2 has no irreducible proper coloring.
Proof. Let f : VG2 → C be a C-irreducible proper coloring of G2, i.e., a map such that
f(x) 6= f(y) if {x, y} ∈ EG2 and (∀c1, c2 ∈ C)f−1(c1) ∪ f−1(c2) is dependent. Similar
to the proof of Theorem 4.2((2)⇒(1)), f−1(c) is finite for all c ∈ C, and f [
⋃
n∈ω\{0}An]
is infinite. Fix c0 ∈ f [
⋃
n∈ω\{0}An]. Then Index(f
−1(c0)) = {n ∈ ω\{0} : f−1(c0) ∩
An 6= ∅} is finite. So there exists some
c1 ∈ f [
⋃
n∈ω\{0}An]\
⋃
m∈Index(f−1(c0))(f [Am] ∪ f [Am−1] ∪ f [Am+1])
as
⋃
m∈Index(f−1(c0))(f [Am]∪ f [Am−1]∪ f [Am+1]) is finite. Clearly, f
−1(c0)∪ f−1(c1)
is independent, and we obtain a contradiction.
(3)⇒(1) Assume A as in the proof of (2)⇒(1). Let G12 be the infinite locally finite
connected graph obtained from G2 of (2)⇒(1) after deleting t and {{t, x} : x ∈ A1}.
Consider a minimal dominating set D of G12. The following conditions must be satisfied:
(i) Since D is a dominating set, for each n ∈ ω \ {0, 1}, there is an a ∈ D such that
a ∈ An−1 ∪ An ∪ An+1 (otherwise, no vertices from An belongs to D or have a
neighbor in D).
(ii) By the minimality of D, we have |An ∩D| ≤ 1 for each n ∈ ω \ {0}.
Clearly, (i) and (ii) determine a partial choice function overA, contradicting the assumption
that A has no partial choice function.
(4)⇒(1) Let A = {An : n ∈ ω} be a disjoint countably infinite set of non-empty
finite sets and let A =
⋃
n∈ω An. Consider a countably infinite family (Bi, <i)i∈ω of
well-ordered sets such that the following hold (cf. the proof of [5, Theorem 1, Remark 6]):
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 13
(i) |Bi| = |Ai|+k for some fixed 1 ≤ k ∈ ω and thus, there is no mapping with domain
Ai and range Bi.
(ii) for each i ∈ ω, Bi is disjoint from A and the other Bj’s.
LetB =
⋃
i∈ω Bi. Pick a countably infinite sequence T = {ti : i ∈ ω} disjoint fromA
and B and consider the following infinite locally finite connected graph G3 = (VG3 , EG3)
(see Figure 4):
VG3 := A ∪B ∪ T,
EG3 :=
{
{ti, ti+1} : i ∈ ω
}
∪
{
{ti, x} : i ∈ ω, x ∈ Ai
}
∪
{
{x, y} : i ∈ ω, x ∈ Ai, y ∈ Bi
}
.
• • ...
A0
•
t0
(B0, <0)
• • ...
• • ...
A1
•
t1
(B1, <1)
• • ...
• • ...
A2
(B2, <2)
• • ...
•
t2
...
...
...
Figure 4: Graph G3.
By assumption, G3 has a minimal edge cover, say G′3. For each i ∈ ω, let fi : Bi →
P(Ai)\{∅} map each vertex of Bi to its neighborhood in G′3.
Claim 5.3. Fix i ∈ ω. For any two distinct 1 and 2 in Bi, |fi(1) ∩ fi(2)| ≤ 1.
Proof. This follows from the fact that G′3 does not contain a complete bipartite subgraph
K2,2. In particular, each component of G′3 has at most one vertex of degree greater than 1.
If any edge e ∈ G′3 has both of its endpoints incident on edges of G′3\{e}, then G′3\{e} is
also an edge cover of G3, contradicting the minimality of G′3.
By Fact 3.1(2) and (i), there are tuples (′1, 
′
2) ∈ Bi×Bi such that fi(′1)∩fi(′2) 6= ∅.
Consider the first such tuple (′′1 , 
′′
2) with respect to the lexicographical ordering ofBi×Bi.
Then {fi(′′1) ∩ fi(′′2) : i ∈ ω} is a choice function of A by Claim 5.3.
(5)⇒(1) Assume A, and A as in the proof of (4)⇒(1). Let R = {rn : n ∈ ω} and
T = {tn : n ∈ ω} be two disjoint countably infinite sequences disjoint from A. We define
the following locally finite connected graph G4 = (VG4 , EG4) (see Figure 5):
VG4 := (
⋃
n∈ω
An) ∪R ∪ T,
EG4 :=
{
{tn, tn+1} : n ∈ ω
}
∪
{
{tn, x} : n ∈ ω, x ∈ An
}
∪
{
{rn, x} : n ∈ ω, x ∈ An
}
.
14 Ars Math. Contemp. 24 (2024) #P4.06
• • • ...
•
r0
A0
•
t0
• • • ...
•
r1
A1
•
t1
...
...
Figure 5: Graph G4.
Let M be a maximal matching of G4. For all i ∈ ω, there is at most one x ∈ Ai
such that {ri, x} ∈ M since M is a matching and there is at least one x ∈ Ai such that
{ri, x} ∈ M since M is maximal. These unique x ∈ Ai determine a choice function for
A.
This concludes the proof of the Theorem.
6 Remarks on new equivalents of AC
Remark 6.1. We remark that the statement “Any connected graph has a minimal dominat-
ing set” implies AC.6 Consider a family A = {Ai : i ∈ I} of pairwise disjoint non-empty
sets. For each i ∈ I , let B0i = Ai×{0} and B1i = Ai×{1}. Pick t 6∈
⋃
i∈I B
0
i ∪
⋃
i∈I B
1
i
and consider the following connected graph G5 = (VG5 , EG5) in Figure 6:
VG5 := {t} ∪
⋃
i∈I
B0i ∪
⋃
i∈I
B1i ,
EG5 :=
{
{x, t} : i ∈ I, x ∈ B0i
}
∪
{
{x, y} : i ∈ I, x ∈ B0i , y ∈ B1i
}
∪
{
{x, y} : i ∈ I, x, y ∈ B0i , x 6= y
}
∪
{
{x, y} : i ∈ I, x, y ∈ B1i , x 6= y
}
.
• • • ...
B10
• • • ...
B11
• • • ...
B12
• • • ...
B00 • • • ...
B01 • • • ...
B02
•
t
...
...
Figure 6: Graph G5, a connected graph. If each Ai is finite, then G5 is rayless.
6The authors are very thankful to one of the referees for pointing out to us an error that appeared in this remark
in a former version of the paper and especially for guiding us to eliminate the error.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 15
Let D be a minimal dominating set of G5. Define Mi = (B0i ∪ B1i ) ∩ D for every
i ∈ I . We claim that for every i ∈ I , |Mi| = 1.
Case (i): If there exists an i ∈ I such that Mi = ∅, then any member of B1i is neither in
D nor it has a neighbour in D. This contradicts the fact that D is a dominating set of G5.
Case (ii): If there exists an i ∈ I such that |Mi| ≥ 2, then pick x, y ∈Mi.
• Case (ii(a)): If x, y ∈ B0i , or x, y ∈ B1i , then D\{x} is a dominating set, which
contradicts the minimality of D.
• Case (ii(b)): If x ∈ B0i , and y ∈ B1i , then D\{y} is a dominating set, which contra-
dicts the minimality of D. Similarly, we can obtain a contradiction if y ∈ B0i , and
x ∈ B1i .
Let Mi = {ai} for every i ∈ I . Define,
g(i) =
{
p1i (ai) if ai ∈ B1i ∩D,
p0i (ai) if ai ∈ B0i ∩D,
where for m ∈ {0, 1}, pmi : Bmi → Ai is the projection map to the first coordinate for
each i ∈ I . Then, g is a choice function for A.
Remark 6.2. The statement “Any connected bipartite graph has a minimal edge cover”
implies AC. Assume A = {Ai : i ∈ I} as in the proof of Remark 6.1. Consider a
family {(Bi, <i) : i ∈ I} of well-ordered sets with fixed well-orderings such that for each
i ∈ I , Bi is disjoint from A =
⋃
i∈I Ai and the other Bj’s, and there is no mapping with
domain Ai and range Bi (see the proofs of [5, Theorem 1] and Theorem 5.1((4)⇒(1))).
Let B =
⋃
i∈I Bi. Then given some t 6∈ B ∪ (
⋃
i∈I Ai), consider the following connected
bipartite graph G6 = (VG6 , EG6) in Figure 7:
VG6 := {t} ∪B ∪ (
⋃
i∈I
Ai),
EG6 :=
{
{x, t} : i ∈ I, x ∈ Ai
}
∪
{
{x, y} : i ∈ I, x ∈ Ai, y ∈ Bi
}
.
• • ...
A1
(B1, <1)
• • ...
• • ...
A2
• ...
t
(B2, <2)
• • ...
...
...
...
...
• • ...
An
(Bn, <n)
• • ...
Figure 7: Graph G6, a connected bipartite graph. If each Ai is finite, then G6 is rayless.
The rest follows from the arguments of the implication (4)⇒(1) in Theorem 5.1.
16 Ars Math. Contemp. 24 (2024) #P4.06
Remark 6.3. The statement “Any connected bipartite graph has a maximal matching”
implies AC. Assume A as in the proof of Remark 6.1. Pick a sequence T = {tn : n ∈ I}
disjoint from
⋃
i∈I Ai, a t 6∈
⋃
i∈I Ai ∪ T and consider the following connected bipartite
graph G7 = (VG7 , EG7) in Figure 8:
VG7 :=
⋃
i∈I
Ai ∪ T ∪ {t}, EG7 :=
{
{ti, x} : x ∈ Ai
}
∪
{
{t, ti} : i ∈ I
}
.
• • • ...
A0
•t0
• • • ...
A1
•t1
• • • ...
A2
•t2
...
...
t
•
Figure 8: Graph G7, a connected rayless bipartite graph.
Let M be a maximal matching of G7. Clearly, S = {i ∈ I : {ti, t} ∈ M} has at
most one element and for each j ∈ I\S, there is exactly one x ∈ Aj (say xj) such that
{x, tj} ∈ M . Let f(Aj) = xj for each j ∈ I\S. If S 6= ∅, pick any r ∈ Ai if i ∈ S,
since selecting an element from a set does not involve any form of choice. Let f(Ai) = r.
Clearly, f is a choice function for A.
Theorem 6.4 (ZF). The following statements are equivalent:
(1) AC
(2) Any connected graph has a minimal dominating set.
(3) Any connected bipartite graph has a maximal matching.
(4) Any connected bipartite graph has a minimal edge cover.
Proof. Implications (1)⇒(2)–(4) are straightforward (cf. Proposition 3.3). The other di-
rections follow from Remarks 6.1, 6.2, and 6.3.
Remark 6.5. The locally finite connected graphs forbid those graphs that contain vertices
of infinite degrees but may contain rays. There is another class of connected graphs that
forbid rays but may contain vertices of infinite degrees. For a study of some properties of
the class of rayless connected graphs, the reader is referred to Halin [8].
(1). We can see that the statement “Every connected rayless graph has a minimal dom-
inating set” implies ACfin. Consider a non-empty family A = {Ai : i ∈ I} of pairwise
disjoint finite sets and the graphG5 from Remark 6.1. Clearly,G5 is connected and rayless.
The rest follows by the arguments of Remark 6.1.
(2). By applying Remark 6.3 and Proposition 3.3, we can see that the statement “Every
connected rayless graph has a maximal matching” is equivalent to AC.
(3). The statement “Every connected rayless graph has a minimal edge cover” implies
ACfin. Let A = {Ai : i ∈ I} be as in (1) and G6 be the graph from Remark 6.2. Then G6
is connected and rayless. By the arguments of Remark 6.2, the rest follows.
A. Banerjee et al.: Distinguishing colorings, proper colorings, and covering properties . . . 17
7 Questions
Question 7.1. Do the following statements imply AC (without assuming that the sets of
colors can be well-ordered)?
(1) Any graph has a chromatic index.
(2) Any graph has a distinguishing number.
(3) Any graph without a component isomorphic to K1 or K2 has a distinguishing index.
Stawiski [20, Theorem 3.8] proved that the statements (1)–(3) mentioned above are equiv-
alent to AC by assuming that the sets of colors can be well-ordered.
ORCID iDs
Amitayu Banerjee https://orcid.org/0000-0003-4156-7209
Zalán Molnár https://orcid.org/0000-0002-4391-246X
Alexa Gopaulsingh https://orcid.org/0000-0001-8684-5028
References
[1] L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hun-
gar. 29 (1977), 193–200, doi:10.1007/BF01896481, https://doi.org/10.1007/
BF01896481.
[2] A. Banerjee, Maximal independent sets, variants of chain/antichain principle and cofinal
subsets without AC, Comment. Math. Univ. Carolin. 64 (2023), 137–159, doi:10.14712/
1213-7243.2023.028, https://doi.org/10.14712/1213-7243.2023.028.
[3] A. Banerjee, Partition models, permutations of infinite sets without fixed points, and weak
forms of AC, 2023, arXiv:2109.05914v4 [math.LO], to appear in Comment. Math.
Univ. Carolin.
[4] O. De la Cruz, E. J. Hall, P. Howard, K. Keremedis and J. E. Rubin, Unions and the axiom of
choice, Math. Log. Q. 54 (2008), 652–665, doi:10.1002/malq.200710073, https://doi.
org/10.1002/malq.200710073.
[5] C. Delhommé and M. Morillon, Spanning graphs and the axiom of choice, Rep. Math. Logic
40 (2006), 165–180.
[6] H. M. Friedman, Invariant maximal cliques and incompleteness (2011), Manuscript
No. 70, 132 pp., Downloadable Manuscripts, https://u.osu.edu/friedman.8/
foundational-adventures/downloadable-manuscripts/.
[7] F. Galvin and P. Komjáth, Graph colorings and the axiom of choice, Period. Math. Hungar. 22
(1991), 71–75, doi:10.1007/BF02309111, https://doi.org/10.1007/BF02309111.
[8] R. Halin, The structure of rayless graphs, Abh. Math. Sem. Univ. Hamburg 68 (1998), 225–253,
doi:10.1007/BF02942564, https://doi.org/10.1007/BF02942564.
[9] H. Herrlich and Y. T. Rhineghost, Graph-coloring and choice. A note on a note by Shelah
and Soifer, Quaest. Math. 28 (2005), 317–319, doi:10.2989/16073600509486131, https:
//doi.org/10.2989/16073600509486131.
[10] H. Herrlich and E. Tachtsis, On the number of Russell’s socks or 2+2+2+ · · · =?, Comment.
Math. Univ. Carolin. 47 (2006), 707–717, https://dml.cz/handle/10338.dmlcz/
119630.
18 Ars Math. Contemp. 24 (2024) #P4.06
[11] H. Höft and P. Howard, A graph theoretic equivalent to the axiom of choice, Z. Math. Logik
Grundlagen Math. 19 (1973), 191, doi:10.1002/malq.19730191103, https://doi.org/
10.1002/malq.19730191103.
[12] P. Howard and J. E. Rubin, Consequences of the Axiom of Choice, volume 59 of Mathematical
Surveys and Monographs, American Mathematical Society, Providence, RI, 1998, doi:10.1090/
surv/059, https://doi.org/10.1090/surv/059.
[13] T. J. Jech, The Axiom of Choice, volume 75 of Studies in Logic and the Foundations of Math-
ematics, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing
Co., Inc., New York, 1973.
[14] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge-colourings, European J. Comb.
45 (2015), 124–131, doi:10.1016/j.ejc.2014.11.003, https://doi.org/10.1016/j.
ejc.2014.11.003.
[15] A. Lévy, Basic Set Theory, Dover Publications, Inc., Mineola, NY, 2002, reprint of the 1979
original [Springer, Berlin].
[16] D. Marker, Model Theory: An Introduction, volume 217 of Graduate Texts in Mathematics,
Springer-Verlag, New York, 2002, doi:10.1007/b98860, https://doi.org/10.1007/
b98860.
[17] S. Shelah and A. Soifer, Axiom of choice and chromatic number of the plane, J. Comb. Theory
Ser. A 103 (2003), 387–391, doi:10.1016/S0097-3165(03)00102-X, https://doi.org/
10.1016/S0097-3165(03)00102-X.
[18] R. M. Solovay, A model of set-theory in which every set of reals is Lebesgue measurable,
Ann. of Math. (2) 92 (1970), 1–56, doi:10.2307/1970696, https://doi.org/10.2307/
1970696.
[19] C. Spanring, Axiom of choice, maximal independent sets, argumentation and dialogue games,
in: 2014 Imperial College Computing Student Workshop (ICCSW 2014), Schloss Dagstuhl –
Leibniz Zentrum für Informatik, Wadern, pp. 91–98, 2014, doi:10.4230/OASIcs.ICCSW.2014.
91, https://doi.org/10.4230/OASIcs.ICCSW.2014.91.
[20] M. Stawiski, The role of the axiom of choice in proper and distinguishing colourings, Ars
Math. Contemp. 23 (2023), Paper No. 10, 8 pp., doi:10.26493/1855-3974.2863.4b9, https:
//doi.org/10.26493/1855-3974.2863.4b9.