The extremal-graph-theory tag has no wiki summary.

**24**

votes

**3**answers

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

**21**

votes

**4**answers

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

**16**

votes

**1**answer

729 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**15**

votes

**2**answers

810 views

### Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...

**14**

votes

**2**answers

760 views

### Largest graphs of girth at least 6

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
...

**13**

votes

**1**answer

455 views

### Induced Paths of Order 4

In a graph $G=(V,E)$ of order $n$, what fraction of the $\binom{n}{4}$ $4$-subsets of $V$ can induce the path of order four?
I looked at this question 30 years ago and was never able to come up with ...

**11**

votes

**2**answers

441 views

### Strongly connected directed graphs with large directed diameter and small undirected diameter?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...

**10**

votes

**1**answer

443 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...

**9**

votes

**2**answers

695 views

### Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum ...

**8**

votes

**5**answers

1k views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**8**

votes

**1**answer

408 views

### What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?

In Zsolt Tuza's Unsolved combinatorial problems I, Problem 46 is the following conjecture:
Let $G$ be a graph on $n$ vertices. Let $\alpha_1$ be the maximum number of edges of $G$ such that every ...

**8**

votes

**1**answer

390 views

### What is the state of the art for the Turán number of $K_{4,4}$?

In Chung and Graham's "Erdős on Graphs: His legacy of unsolved problems," they discuss several open problems concerning Turán numbers for bipartite graphs.
There is a construction which gives graphs ...

**8**

votes

**1**answer

211 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**8**

votes

**1**answer

276 views

### Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

This problem in some ways related to this post.
Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the ...

**8**

votes

**0**answers

181 views

### How many n/2-cycles can a cubic graph have

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?
A random cubic graph has ...

**7**

votes

**4**answers

347 views

### Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...

**7**

votes

**1**answer

414 views

### Graphs with many triangles but few complete graphs on 4 vertices

Let $G$ be a graph on $n$ vertices with $an^2$ edges containing at most $an^2/2$ copies of $K_4$. If there are cubically many triangles, say $cn^3$, then there is at least one edge that is not ...

**7**

votes

**1**answer

494 views

### 6-regular bipartite graphs with no 8-cycles

I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist ...

**7**

votes

**0**answers

192 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**6**

votes

**2**answers

365 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**6**

votes

**2**answers

409 views

### Minimal graphs of prescribed girth and chromatic number

The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...

**6**

votes

**2**answers

483 views

### Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature.
Let G be a finite, simple, connected graph. Let the ...

**6**

votes

**1**answer

266 views

### Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of ...

**6**

votes

**1**answer

366 views

### On Turan's theorem

Turan's theorem provides minimum number of edges of a graph on $n$ vertices to surely contain a clique of a prescribed size. This has been generalized to regular graphs.
What additional ...

**6**

votes

**1**answer

177 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**6**

votes

**1**answer

139 views

### Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
...

**6**

votes

**1**answer

331 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**6**

votes

**0**answers

356 views

### Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...

**5**

votes

**3**answers

867 views

### Online Library of Unlabeled Connected Graphs on n Vertices

Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...

**5**

votes

**2**answers

258 views

### Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of ...

**5**

votes

**1**answer

482 views

### No big clique minor but a big grid minor

I was wondering if the following result is known (or if there's a nice short proof without treewidth/brenchwidth related theorems): as the title says, suppose you have a graph without a big clique ...

**5**

votes

**1**answer

607 views

### Connected components of large induced subgraphs of hypercubes

Let $H$ be the $n$-dimensional hypercube, i.e. $\{0,1\}^n$ with edges between two vertices if and only if they differ in exactly one co-ordinate. We say that an edge is in direction $i$ if its ...

**5**

votes

**1**answer

545 views

### Characterization of infinite paths in graphs

First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph. A
pair $(\mathcal{G},s)$ is called a ...

**4**

votes

**3**answers

837 views

### Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.
However, ...

**4**

votes

**3**answers

210 views

### Almost all graphs have a subgraph from a large class of graphs with constant order

I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.
I suspect the question might have a very trivial ...

**4**

votes

**1**answer

270 views

### Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...

**4**

votes

**2**answers

193 views

### How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...

**4**

votes

**2**answers

173 views

### Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...

**4**

votes

**1**answer

219 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**4**

votes

**0**answers

417 views

### Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...

**4**

votes

**0**answers

319 views

### An extremal problem for graphs having every edge contained in a 4-clique

This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...

**3**

votes

**1**answer

312 views

### Complete Bipartite Subgraph of Dense Bipartite Subgraph

Q1: Consider a $2^n$ by $2^n$ bipartite graph with at least $(1-\epsilon)2^{2n}$ edges. For any $\epsilon > 0$ and $n$ large enough, is it always possible to find a $2^{(1-f(\epsilon))n}$ by ...

**3**

votes

**1**answer

272 views

### Degree conditions for k-factor

I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, ...

**2**

votes

**3**answers

501 views

### Non-isomorphic graphs with the same numbers of closed walks

Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:
$1)$ $G_i\ncong H_i$ for $i=1, 2, \cdots, n$
$2)$ ...

**2**

votes

**1**answer

382 views

### existence of triangle-free graphs for sparse regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to the half of the number of ...

**2**

votes

**1**answer

379 views

### Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear?
It seems to be a natural problem to ask. but I could not find any reference.
Thanks.

**2**

votes

**2**answers

352 views

### Maximum number of edges $f(n,k)$ in a graph on $n$ vertices with no $k$-core?

The $k$-core of a finite graph is defined as follows. Delete all vertices of degree $< k$ and repeat until there are no such vertices left. If there is a nonempty subgraph remaining, necessarily ...

**2**

votes

**2**answers

171 views

### Complete k-partite graph covers all K_k of a graph

Suppose that we have a complete graph $G$ of $n$ vertices. What is the minimum number of complete $k$-partite graph (subgraph of $G$) that covers all the complete graph of $k$ vertices of $V(G)$? Are ...

**2**

votes

**1**answer

221 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**2**

votes

**1**answer

591 views

### If many triangles share edges, then some edge is shared by many triangles

Let $G=(V,E)$ be a graph.
Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and ...