# Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

46 questions
Filter by
Sorted by
Tagged with
43 views

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

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 ...
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 ...
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 ...
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 ...
31 views

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 ...
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 ...
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 ...
560 views

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 ...
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 \ | \...