Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

43
votes
8answers
4k views

What is a continuous path?

I would like some help, because I am getting mad trying to answer the following Question: Let $X$ be a topological space, what is a continuous path in $X$? Well, maybe you're already getting ...
40
votes
3answers
2k views

History of the four-colour problem

It is stated in many places that the first published reference to the four-colour problem (aka the four-color problem) was an anonymous article in The Athenæum of April 14, 1860, attributed to de ...
40
votes
4answers
3k views

Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
39
votes
5answers
4k views

Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another. My main ...
39
votes
4answers
6k views

Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...
38
votes
1answer
3k views

Why are there 1024 Hamiltonian cycles on an icosahedron?

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron. By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$. [But see edit below re directed vs. undirected!] ...
34
votes
6answers
3k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
31
votes
1answer
1k views

What is the sandpile torsor?

Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...
30
votes
5answers
2k views

Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges? I know that the answer is ...
29
votes
20answers
3k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
29
votes
4answers
784 views

Graph containing all trees?

Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get ...
29
votes
3answers
2k views

How much linear algebra can be done with graphs?

Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of ...
29
votes
1answer
3k views

An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
28
votes
8answers
2k views

Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...
28
votes
3answers
4k views

Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces. Some ways in which they're exceptional: Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
28
votes
0answers
855 views

Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
27
votes
3answers
2k views

Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy. Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
26
votes
4answers
2k views

Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples: 1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...
26
votes
3answers
3k views

Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], ...
26
votes
1answer
1k views

Does this knot invariant distinguish trefoil chiralities?

Let $C_N$ denote the labelled configuration of $N^{th}$ roots of unity with $p_J = e^{\frac{2\pi iJ}{N}}$ for $J = 1\ldots N$. As a corollary of something else I was playing around with, I recently ...
25
votes
12answers
4k views

Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...
25
votes
9answers
2k views

How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings, fields, graphs, partial orders, etc. ...
25
votes
2answers
808 views

Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
24
votes
4answers
2k views

Adjacency matrices of graphs

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the ...
24
votes
3answers
3k views

Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable. This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...
24
votes
3answers
621 views

Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
24
votes
1answer
843 views

Disjoint stable sets in tournaments

Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with ...
23
votes
9answers
2k views

Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
23
votes
15answers
6k views

Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
23
votes
18answers
6k views

Interesting and Accessible Topics in Graph Theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...
23
votes
2answers
2k views

Counting subgraphs of bipartite graphs

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed! Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...
22
votes
4answers
930 views

What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = ...
22
votes
6answers
2k views

Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of ...
22
votes
7answers
3k views

Spectral graph theory: Interpretability of eigenvalues and -vectors

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally ...
22
votes
3answers
1k views

Some models for random graphs that I am curious about

G(n,p) We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
22
votes
1answer
1k views

Rock-paper-scissors…

A directed graph whose underlying undirected graph is complete is called a tournament. Let us call a (finite) directed graph balanced if every vertex has as many incoming as outgoing edges. The ...
22
votes
2answers
1k views

Does this poset have a unique minimal element?

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the ...
21
votes
4answers
905 views

A graph with few edges everywhere

Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue. Suppose the following two conditions hold: for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$ for any ...
21
votes
3answers
682 views

Is the Rado graph a Cayley graph? If so, what is the group like? (And other questions…)

The countable random graph, also known as the Rado graph, is characterized as the unique countable graph in which every two disjoint finite sets $A$ and $B$ of vertices admit a vertex $p$ connected to ...
20
votes
3answers
1k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
20
votes
1answer
1k views

Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
20
votes
1answer
753 views

A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
20
votes
1answer
1k views

Who wins this two-player game based on the sandpile model?

Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an ...
19
votes
4answers
748 views

Hexagonal rooks

Suppose you have a triangular chessboard of size $n$, whose "squares" are ordered triples $(x,y,z)$ of nonnegative integers that add up to $n$. A rook can move to any other point that agrees with it ...
19
votes
2answers
2k views

Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do! The following problem is in Problem 1.F in Van Lint and Wilson: Let $G$ be a graph where every vertex has degree $d$. ...
19
votes
2answers
797 views

Erdős, Harary, Tutte's “dimension of graph”: Progress in last 48 yrs?

I just ran across this delightful paper by an amazing triumvirate: Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20. (Cambridge link) ...
19
votes
3answers
721 views

Probability that random weights on $K_n$ satisfy triangle inequality

Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the ...
19
votes
2answers
992 views

Graphs, K-theory and combinatorial balls: conjectures

The following conjectures from Kapranov and Saito's Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions aren't as well-known as they aught to be, so I'd like to state ...
19
votes
1answer
638 views

Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...
19
votes
0answers
680 views

Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...