# Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

55 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
1 vote
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: ...
1 vote
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 ...
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$?
1 vote
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 ...
1 vote
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 ...
66 views

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 ...
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 ...
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)$ ...
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 ...
216 views

1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
32 views

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 ...
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 ...
1 vote
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 ...