Questions tagged [infinite-graphs]
The study of graphs with an infinite number of vertices.
46
questions
1
vote
1answer
43 views
Monomorphisms Between Infinite Graphs
I'm really curious about this question:
Let $G(V_G,E_G)$ and $H(V_H,E_H)$ be infinite (infinite!, not finite) graphs, such that $$|V_G|=|V_H|,$$ and let $f$, $g$ be functions $f: G\rightarrow H$, $g: ...
0
votes
0answers
21 views
Brooks' theorem in the infinite
Let $G=(V;E)$ be an infinite graph, with $|V|$ an uncountable cardinal. Suppose that the maximum degree of any $v \in V$ is $\kappa$, where $\kappa \leq |V|$ is an infinite cardinal. Does it follow ...
1
vote
1answer
35 views
A new language construction
I'm interested if the following language construction was studied. Let $\Sigma$ be an alphabet and $\Sigma^*$ is the set of all words over $\Sigma$. Consider a directed graph $G=\langle\Sigma^*,E\...
2
votes
1answer
35 views
Does every infinite graph contain a maximal clique?
The original problem is stated in terms of the tolerance relation (reflexive and symmetric, but not necessarily transitive): Is every tolerance subset contained in a maximal tolerance subset?
For a ...
1
vote
1answer
38 views
Determining set and Automorphism group of a graph
Let $G$ be a simple graph. A set $S\subset V(G)$ is said to be determining set of $G$, if for any two Automorphisms $f,g \in Aut(G)$ whenever $f(s)=g(s)$ for all $s\in S$, then $f=g$. That is, an ...
2
votes
1answer
39 views
Finite automorphism group of a graph
Let $G$ be a simple graph and $Aut(G)$ denotes the automorphism group. Then prove or disprove,
Suppose $Aut(G)$ and $diam(G)$ are finite for a graph $G$. Then $|V(G)|$ is finite.
I know $Aut(G)$ ...
2
votes
1answer
34 views
Eccentricity in infinite tournaments
Definitions. A tournament is an oriented complete graph, that is, it's what you get by taking a (finite or infinite) complete graph and assigning a unique direction to each edge. If $T$ is a ...
4
votes
2answers
87 views
If all subgraphs of two graphs are pairwise isomorphic, are the graphs themselves isomorphic?
For two graphs $G,H$ let's write $G\cong H$ if they are isomorphic.
Let's denote the set of all subgraphs of $G$ by $\mathcal S(G)$. Note that $G\in \mathcal S(G)$ and there can be elements $a,b\in \...
0
votes
1answer
50 views
Is there a correspondence between different hyperbolic automorphisms of a regular tree?
First, recall that a regular tree $\mathcal{T}_n$ ($n>1$), is an infinite tree in which every vertex has valency $n$. It is known that the automorphisms of a regular tree can be classified into ...
0
votes
1answer
71 views
How do I apply the infinite Ramsey theorem to graph theory?
The infinite Ramsey theorem reads as such:
Theorem. Let $X$ be some infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists ...
0
votes
1answer
33 views
The minor relation on infinite graphs. [closed]
The minor relation is defined in 1.7, GTM173.
The question is from the exercise 1.24
We already know that the minor relation defines a partial ordering on finite graphs.
Is it true for infinite graphs?...
2
votes
0answers
26 views
Can the (infinite) graph of a tiling of the plane have no two vertices of the same degree?
I mean for each region to have three or more edges in its boundary. If there's a term for that I'd appreciate a comment as to the term. Another way to state this requirement is that the graph not have ...
2
votes
1answer
52 views
How to think of formal derivation $\Gamma \vdash \phi$ in terms of trees/graphs?
According to my text, a finite set of formulas $\Gamma$ in a given language $L$ is derivable, denoted $\vdash \Gamma$, if $\Gamma$ belongs to the least collection of finite sets of formulas, denoted $...
1
vote
1answer
217 views
Does KÅnig's theorem hold for infinite bipartite graphs?
KÅnig's theorem states that in a bipartite graph the size of the maximal matching equals the size of the minimal vertex cover.
I learned it as an equivalence to Hall's theorem and we proved it using ...
4
votes
4answers
159 views
Visual example of an infinite planar graph with degree sequence $(4^4,6^\infty)$
After reading some graph theory and talking with experts, I was intrigued. I would like to construct and visualise an infinite planar graph with degree sequence:
$$D=(4^4,6^\infty)$$
where the ...
1
vote
0answers
72 views
Finite Unions of Dendrites
I will ask the main question first, and then give the motivation for this one! The question is a bit specific, but seems to be the most general question to ask after handling some obvious ...
0
votes
1answer
53 views
Is there a name for graphs with this property?
The property of the graph is the following: it's countable, undirected, simple, and for any infinite subset of vertices there are two vertices connected(by infinite Ramsey theorem this is in fact ...
1
vote
0answers
31 views
non-$n$-colorability of an infinite graph and generic partitions of the vertices
I have an infinite graph $G$ and a natural number $n$, and I am interested in the property of $n$-colorability of $G$. I have the naive idea that
(1) if almost every partition of the vertices of $...
2
votes
2answers
142 views
Does every infinite connected graph contain a ray?
I read a proof that every infinite, connected, locally finite graph contains a ray, and the proof relies on the graph being locally finite. I didn't want to assume that the lack of that condition made ...
1
vote
2answers
79 views
Why does the graph of $y=\frac{\tan(x)/\sin(x)}{\cos(x)}$ have minima at multiples of $\pi$?
I was just messing around is Desmos and plotted the graph of $$y=\frac{\frac{\tan(x)}{\sin(x)}}{\cos(x)}$$ and I realised that all the minimum points on the graph were multiples of $\pi$. Could ...
2
votes
1answer
48 views
Is this proposition a sufficient condition for a countably infinite simple-digraph to be a polytree? If so is it also a necessary condition?
If any countably infinite simple digraph $G$ is such that every weakly connected, spanning subgraph of $G$ is equal to $G$ then must $G$ always be a polytree (an orientation of an undirected tree ...
4
votes
3answers
71 views
What does $\lim\limits_{x \to \infty} f'(x)=3$ mean?
What I did was to see that the function is behaving as a straight line with gradient $3$ at infinity which implies that the function has an oblique asymptote as $x \to \infty$ but my testing portal ...
1
vote
1answer
32 views
Unbounded, Repeated Figures in Non-periodic Tilings
I was just wondering something about non-periodic tilings (of the plane, though I imagine the dimension is irrelevant for finite dimensions; would be interesting if it wasn't!).
I assume we know what ...
1
vote
0answers
30 views
How to find a minimal planar covering of a graph
Every graph has a planar covering graph. In particular, the Universal cover, being a tree, will be planar.
How do we find a minimal planar covering $P$ graph of a graph $G$? By minimal, I mean that ...
15
votes
1answer
567 views
Cantor-Bernstein-Schröder Theorem: small proof using Graph Theory, is this correct?
The theorem:
Suppose there exist injective functions $A \to B$ and $B \to A$ between two inļ¬nite sets $A$ and $B$. Then there exists a bijection $A \to B$.
Proof:
Let $f: A \to B$ and $g: B \to A$...
0
votes
1answer
184 views
How does colorability work in infinite (countable and uncountable) graphs?
Some background:
I know that for finite graphs, iff a graph has no odd cycle (i.e. it is bipartite), it can be $2$-colored. Similarly, a graph without $K_5$ or $K_{3,3}$ is planar, so it can be $4$-...
3
votes
1answer
174 views
Hairy Points in Infinite Graphs (and Peano Continua)
I may have to throw this over to overflow, but I figured I would try here, first. This is a question in continuum theory, but it reduces to a combinatorial/graph-theoretical question. I am highly ...
1
vote
0answers
53 views
Infinite Perfect Graphs
A graph $G$ is perfect if every induced subgraph $H$ of $G$ can be coloured with $k$ colours, where $k$ is the size of a largest clique in $H$.
The Perfect Graph Theorem (conjectured by Berge and ...
0
votes
1answer
43 views
Countable subtrees with given order
Let $T$ be a tree. Let $T^0=T$. For an ordinal $\xi=\eta+1$ we define $T^\xi$ to be the complement of the set of all maximal elements of $T^\eta$. For a limit ordinal $\xi$ we set $T^\xi = \bigcap_{\...
0
votes
1answer
262 views
Hamilton Cycle Theorem?!
I've come across this link, where the author states: "Hamilton Cycle Theorem fails for infinite graphs unless ..."
Please help me on this, what does he mean by "Hamilton Cycle Theorem"? I studied a ...
5
votes
1answer
773 views
There exists no zero-order or first-order theory for connected graphs
Prove that no zero-order theory (i.e. propositional calculus, without quantification) or first-order theory can describe the "connected graph" (i.e. from any point one can reach each other point in ...
1
vote
3answers
122 views
Given a path between 2 vertices of a graph, there is only a finite number of vertices in the path?
Let us have a weighted graph $G=(V,E)$ with set of vertices $V$ and set of edges $E$, with a function $E\to V\times V$, a weight function $w:E\to\mathbb{R}_{>0}$ etc.
Take the topological ...
3
votes
0answers
560 views
Is this proof of the four color theorem for infinite graphs legit?
So you got an infinite planar graph $G$. I will prove that it is four colorable.
So, construct an infinite number of statements about graphs:
The first is "is four colorable"
Next, for each vertex $...
1
vote
2answers
168 views
Is it possible to construct the Rado Graph as a countably infinite graph with non-constant edge probabilities?
Let's say we have a countably infinite set $V$ of vertices and a map $f:V\times{V}\to{(0,1)}$ that assigns to each pair $(i,j)$ of vertices an edge with probability $f(i,j) = p$. I believe that if ...
0
votes
1answer
85 views
Probability that a random graph on countably many vertices is connected
Fix $0 < p < 1$ and let $G$ be a random graph on elements $\mathbb{N}$ where for $n,m \in \mathbb{N}$, the probability that there is an edge between $n$ and $m$ will $p$. What is the probability ...
2
votes
2answers
359 views
Confusion between spectral radius of matrix and spectral radius of the operator
The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of https://en.wikipedia.org/wiki/...
4
votes
2answers
408 views
Labelings of infinite directed acyclic graphs
Let $G=(V,E)$ be a countably infinite directed acyclic graph and $L$ be a finite set of vertex labels. The number $\left|V\right|$ of vertices is countable infinity and some vertices may have an ...
2
votes
1answer
73 views
How to computably reduce the number of colors in (infinite) Ramsey's theorem
Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a 3-...
-1
votes
1answer
880 views
Is there infinite number between two integers?
With more specific saying,
if there is a function that is in continuum from a to b, a and b are real numbers, and bijective to its range, is the number of the function's range infinite?
If it is, ...
5
votes
1answer
176 views
Why is it so difficult to obtain the spectral properties related to infinite matrices, especially when they are not symmetric?
I believe most of the spectral theory is revolving around the bounded self-adjoint linear operators being analogous to real symmetric infinite matrices. Whereas, there are cases when the matrices are ...
-2
votes
1answer
82 views
A Question Regarding Representing $\mathscr P$($\omega$) as a Digraph and CH
It is well known that one can represent sets as digraphs. What is the proper digraph representation of $\mathscr P$($\omega$)? I ask this because $\mathscr P$($\omega$) is $\Pi_1$ in the Levy ...
1
vote
1answer
34 views
Clarification from a proof that a certain type of graph can be endowed with a group operation
I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property.
I'll just throw some definitions here first...
Definitions.
An alphabet $A$ is a ...
1
vote
1answer
527 views
Example of infinite graph
First of all, I review some terms and notations. Let set of all ends of graph $G$ be $\Omega(G)$.
For every end $\omega$ and every finite set $S\subseteq V(G)$, there is a unique component $C(S, \...
7
votes
1answer
190 views
Graphs with uncountably many vertices
Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
24
votes
4answers
705 views
Is this graph connected
Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$:
Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written $a \ \mathcal{R} \ b)$ if and only if $a+b \ | \...
6
votes
1answer
147 views
Killer Tree! (one of my old questions)
There is a problem that killed me! but I couldn't solve it:
We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.
