25 votes
Accepted

Is the Robertson–Seymour theorem equivalent to the compactness of some topological space?

The Robertson–Seymour graph minor theorem states that the set of all (isomorphism classes of) finite undirected graphs under the graph minor relation is a well-quasi-ordering (or wqo for short). It ...
Timothy Chow's user avatar
  • 78.1k
25 votes

Non-definability of graph 3-colorability in first-order logic

Here is one way to do it. 2-colorability case. First let's warm up with the 2-colorability case. Notice that odd-length cycles are not 2-colorable, since the colors have to alternate as you go around ...
Joel David Hamkins's user avatar
21 votes

Brute force open problems in graph theory

The existence of a 57-regular "Moore graph" is one such problem. We define the diameter of a graph $G$ to be the least $l$ such that any two vertices $u,v$ have a path between them using $\...
21 votes
Accepted

Parity and the Axiom of Choice

The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another ...
bof's user avatar
  • 11.5k
18 votes
Accepted

Universal graph

I think that the answer is negative. Assume that such graph $G$ on the vertex set $\{v_1,v_2,\ldots\}$ exists. We construct our not-embeddable graph $H$ on $\{1,2,\ldots\}$ by steps. On the $i$-th ...
Fedor Petrov's user avatar
16 votes

Who is M. Meyniel?

This "M. Meyniel" is indeed, and definitively, Henri Meyniel (sometimes spelled Henry Meyniel). Note that the article you mention was communicated by Berge, at a time (1972) when Meyniel was ...
Greg82's user avatar
  • 261
16 votes

Brute force open problems in graph theory

Elaborating on the comment of Wojowu, for what positive integers $q$ does there exist a bipartite graph $G$ with vertex bipartition $(A,B)$ satisfying: (a) $|A|=|B|=q^2+q+1$, (b) $G$ is regular of ...
16 votes
Accepted

Connected graphs isomorphic to their own contraction

No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension ...
paste bee's user avatar
  • 1,346
16 votes
Accepted

Scrambling a “Connections” grid

Yes, here is one solution for the 4-by-4 case found by a computer search. Each array is obtained from the previous one by applying the permutation (0 1 2 3 4)(5 6 7 8 9)(10 11 12 13 14) to the entries....
Ed Kirkby's user avatar
  • 176
15 votes

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

This is false as shown by the following digraph. From $x$ there is an edge to $v_p$, from $v_p$ there is a cycle of length $p$ to itself, and from $v_p$ there are $p-1$ different paths to $y$, of ...
domotorp's user avatar
  • 18.3k
15 votes

Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula

The problem is that for a complete graph, $\mu_{n-1} \leq \delta$ is wrong, and thus $f(\delta) < f(\mu_{n+1})$. This can be fixed by adding a special case for the complete graph (for other graphs $...
Command Master's user avatar
14 votes

Is End() a functor from the category of directed graphs to the category of monoids?

No, this isn’t possible. If $\newcommand{\End}{\mathrm{End}}\newcommand{\Aut}{\mathrm{Aut}}\End(-)$ extended to a functor on arbitrary maps of graphs, that would imply that whenever $G$ embeds as a ...
Peter LeFanu Lumsdaine's user avatar
13 votes

Connected graphs isomorphic to their own contraction

No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$). If you collapse a subset containing $0$, the collapsed vertex can ...
Vincent's user avatar
  • 181
12 votes

Brute force open problems in graph theory

Question: Does $K_{50}$ decompose into seven copies of the Hoffman-Singleton graph? The following is copied from https://faculty.math.illinois.edu/~west/openp/hoffsing.html Definitions: The Hoffman-...
12 votes

Does every big polyomino contain a big arithmetic progression?

Alternative proof to Zachs, with best bound: The answer is no, and the largest $k$ possible is $k=4$. The proof is due to a theorem by Dekking from 1978: There exists a sequence on two symbols in ...
Renan's user avatar
  • 121
11 votes
Accepted

Random sample of spanning trees

One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree ...
Tony Huynh's user avatar
  • 31.5k
11 votes

A starting point for research in Graph Theory as a high schooler

I feel that you are asking two questions. (A) How to get started in research? and (B) What are some good books (for a high school student) in graph theory? Question (A) is in scope for mathoverflow, ...
10 votes

Postal code numbering adjacency problem

If there are four regions, three of which border the fourth but don't share a border with each other, then it's easy to see that there can't be any such numbering. EDIT ––– I'm beginning to think this ...
Gerry Myerson's user avatar
10 votes
Accepted

Desargues ten point configuration $D_{10}$ in LaTeX

This example shows that $s\le 2$ and for this $s$, $c\le 3$. Note that we are lucky with the latter, because there is a configuration for which every combinatorially equivalent realization has at ...
Alex Ravsky's user avatar
  • 4,102
10 votes
Accepted

Is there an algorithm to generate graphs with given order and diameter?

About 58% of the graphs on 12 vertices have diameter 3, so filtering a complete generation will be as fast as any. On 20 vertices the fraction has dropped to about 31% but the total is so vast that ...
Brendan McKay's user avatar
10 votes

Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?

This is a limited partial answer to the question ruling out the case where the graph is regular and has four distinct eigenvalues, so the spectrum is $\{k, (\sqrt{2})^a, (-\sqrt{2})^a, -k\}$. van Dam'...
Gordon Royle's user avatar
  • 12.3k
10 votes

How to effectively search Internet for graphs not for function graphs?

Use Google Scholar instead of plain Google; I simply entered graphs and pretty much all the items returned by Google Scholar refer to graphs in the mathematical context. It also suggests helpful ...
Carlo Beenakker's user avatar
10 votes
Accepted

Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4

Brinkmann and McKay's program plantri can generate planar quadrangulations, which are planar graphs with all faces of size 4. If you generate these on 23 vertices ...
Gordon Royle's user avatar
  • 12.3k
9 votes

Girth 5 graphs with diameter 2

No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in R. Singleton, "There is no irregular Moore ...
Gjergji Zaimi's user avatar
9 votes

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

domotorp's lovely solution is by far the best one, but here is an explicit counterexample for $n = 10$, I wonder if it's computationally tractable to figure out the max $n$ for which your statement ...
Ronnie Pavlov's user avatar
9 votes

Two arcs in the complement of a disc must intersect?

Amplitwist's solution just with Jordan: Consider the curves on the Riemann sphere $S$ and connect $\pm 1$ along the real interval $R$ inside the disk such that $R \cup B$ is a closed curve on $S$. ...
Karl Fabian's user avatar
  • 1,546
9 votes
Accepted

Does every big polyomino contain a big arithmetic progression?

The answer is no. I will construct a connected subset $S\subset \Bbb{Z}^2$ without arbitrarily long arithmetic progressions. Since the grid is locally finite, $S$ must contain an infinite path $P\...
Zach Hunter's user avatar
  • 3,393
8 votes

Why $K_5$ and $K_{3,3}$?

I have now found a paper by A. Skopenkov where he proves the theorem from the fact that $K_5$ and $K_{3,3}$ are the only graphs $G$ with the property For each edge $x y$, the Graph $G - x - y$ does ...
rimu's user avatar
  • 749
8 votes
Accepted

Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$

It certainly tends to $0$. The way to see it almost without any computation is to mark any $n$ disjoint edges. Then, when deciding the fate of the remaining edges, each vertex has $p=2^{2-2n}{2n-2\...
fedja's user avatar
  • 59.5k
8 votes
Accepted

Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. The required embedding $f$ is easy to define. ...
Tony Huynh's user avatar
  • 31.5k

Only top scored, non community-wiki answers of a minimum length are eligible