All Questions
Tagged with axiom-of-choice graph-theory
8
questions
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
1
vote
1
answer
84
views
Maximizing "happy" vertices in splitting an infinite graph
This question is motivated by a real life task (which is briefly described after the question.)
Let $G=(V,E)$ be an infinite graph. For $v\in V$ let $N(v) = \{x\in V: \{v,x\}\in E\}$. If $S\subseteq ...
4
votes
0
answers
127
views
Graphs without maximal vertex-transivite subgraphs
The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-...
3
votes
1
answer
143
views
Ascending chain of vertex-transitive graphs
For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x, y\in X\text{ and } x\neq y\big\}$.
Let $G=(V,E)$ be a simple, undirected graph, and suppose ${\cal V}$ is a collection of subsets of $V$ such that ...
6
votes
1
answer
236
views
Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?
Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image ...
- 2,506
10
votes
1
answer
2k
views
Does the axiom of choice follow from the statement "Every simple undirected graph is either connected, or its complement is connected"?
Using the Well-Ordering Principle, which is equivalent to the Axiom of Choice, it can be proved that
(S): for every simple, undirected graph $G$, finite or infinite, either $G$ or its ...
3
votes
1
answer
903
views
Existence of Spanning Tree implies Well Ordering Principle
Every connected graph has a spanning tree.
Every non-empty set can be well ordered.
Basically I am trying to show that statement 1 implies statement 2. What I tried is as following:
Let $X \ne \...
user81529
15
votes
1
answer
1k
views
Weakest choice principle required for Robertson-Seymour Graph Minor Theorem?
The main Robertson-Seymour Theorem states that finite graphs form a well-quasi-ordering under the graph minor relation. In other words, in every infinite set of finite graphs, there exist two graphs $...
- 2,330