Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

Filter by
Sorted by
Tagged with
0 votes
1 answer
27 views

Example of a locally finite graph without a uniform degree bound

We call an infinite graph locally finite if every vertex of it is of finite degree. A locally finite graph is said to have a uniform degree bound if the degree of every vertex of it is bounded by some ...
user avatar
0 votes
1 answer
39 views

Finding an isomorphism between an infinite tree and a subgraph of $\mathbb{Z}^3$

I was wondering if there exists a construction of an infinite tree, with some properties, that is isomorphic to subgraph of $\mathbb{Z}^3$. Notation Let $\Gamma_n$ denote the tree's vertices at ...
user avatar
  • 1,956
3 votes
1 answer
96 views

Infinite core graphs

Let $G$ be an infinite graph (directed, loops okay, no multi-edges, so essentially a set with a binary relation). $G$ is called core if every one of its endomorphisms is surjective. Does this ever ...
user avatar
3 votes
0 answers
88 views

Compactness argument for countable subgraphs and beyond

I am interested whether there exists a certain generalization of so-called compactness argument in graph theory. First let me define what I mean by "compactness argument" Let $G = (V, E)$ be ...
user avatar
1 vote
0 answers
35 views

Vertex sets separated only by infinitely many vertices imply an infinite number of disjoint paths between them.

In Reinhard Diestel's book "Graph Theory" (5th ed.) there is a chapter on infinite graphs (chapter 8). In that chapter Diestel states the following fact related to Menger's Theorem: ...
user avatar
1 vote
0 answers
34 views

Infinite game (Ehrenfeucht-Fraïssé?) for Linear Temporal Logics

Imagine we have two LTL formulae: A and B. I would like to prove whether they are equivalent or not (the formulae can have the "Globally" operator, so the game is infinite). To do so I have ...
user avatar
  • 141
3 votes
0 answers
114 views

Is there a locally finite tree having every other locally finite tree as a subgraph?

Is there a locally finite tree $T$ such that any locally finite tree is isomorphic to a subgraph of $T$?
user avatar
  • 39
1 vote
2 answers
41 views

Differentiating condition for two infinite graphs

From the tiling of $\mathbb{R}^2$ with squares I get an infinite graph where each node has 4 neighbors. I can create an infinite tree by attaching 4 nodes to a root node and then keep attaching 3 new ...
user avatar
  • 549
1 vote
0 answers
352 views

Infinite recursive graphs and different ways to build them

Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications. They can be identified with binary relations, in other words as elements of the power set ...
user avatar
  • 341
2 votes
1 answer
66 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: ...
user avatar
  • 1,461
0 votes
0 answers
64 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 ...
user avatar
2 votes
1 answer
42 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\...
user avatar
2 votes
1 answer
42 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 ...
user avatar
  • 23
0 votes
1 answer
48 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 ...
user avatar
  • 572
2 votes
1 answer
62 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)$ ...
user avatar
  • 572
2 votes
1 answer
65 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 ...
user avatar
  • 70.1k
4 votes
2 answers
216 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 \...
user avatar
  • 2,785
0 votes
1 answer
80 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 ...
user avatar
0 votes
1 answer
136 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 ...
user avatar
  • 2,785
0 votes
1 answer
70 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?...
user avatar
2 votes
0 answers
33 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 ...
user avatar
  • 6,647
2 votes
1 answer
61 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 $...
user avatar
  • 1,829
1 vote
1 answer
497 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 ...
user avatar
  • 50
4 votes
4 answers
264 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 ...
user avatar
  • 725
6 votes
1 answer
379 views

Finite Unions of Dendrites [closed]

The question is a bit specific, but seems to be the most general question to ask after handling some obvious counterexamples. Initially, I was wondering the following. Let $X$ be a one-dimensional ...
user avatar
0 votes
1 answer
66 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 ...
user avatar
  • 1,251
1 vote
0 answers
32 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 $...
user avatar
  • 7,230
2 votes
2 answers
194 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 ...
user avatar
  • 31
1 vote
2 answers
143 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 ...
user avatar
  • 166
2 votes
1 answer
65 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 ...
user avatar
4 votes
3 answers
95 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 ...
user avatar
2 votes
1 answer
56 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 ...
user avatar
1 vote
0 answers
31 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 ...
user avatar
  • 9,520
19 votes
1 answer
797 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 infinite sets $A$ and $B$. Then there exists a bijection $A \to B$. Proof: Let $f: A \to B$ and $g: B \to A$...
user avatar
0 votes
1 answer
358 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$-...
user avatar
3 votes
1 answer
198 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 ...
user avatar
1 vote
0 answers
72 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 ...
user avatar
0 votes
1 answer
46 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_{\...
user avatar
  • 15.3k
0 votes
1 answer
293 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 ...
user avatar
6 votes
1 answer
1k 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 ...
user avatar
  • 2,950
1 vote
3 answers
176 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 ...
user avatar
  • 871
3 votes
0 answers
696 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 $...
user avatar
  • 9,520
2 votes
2 answers
195 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 ...
user avatar
0 votes
1 answer
103 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 ...
user avatar
  • 750
2 votes
2 answers
491 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/...
user avatar
  • 143
4 votes
2 answers
517 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 ...
user avatar
  • 63
2 votes
1 answer
77 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-...
user avatar
  • 7,230
-1 votes
1 answer
1k 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, ...
user avatar
5 votes
1 answer
228 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 ...
user avatar
  • 143
-2 votes
1 answer
84 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 ...
user avatar