20
votes

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

although short proofs with a tricky application of the Cauchy–Schwarz inequality are known.
Erm... What's the point of using such high-tech as Cauchy-Schwarz on an elementary algebra problem?
WLOG $\...

15
votes

### Are all almost regular graphs obvious?

Here is an expansion of joro's answer.
Claim.
$K_{n, n+1}$ is obvious if and only if $n+1$ is even.
Proof. If $n+1$ is even, we can add a perfect matching on the vertices on the right to obtain a $...

14
votes

Accepted

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

Before giving a very short Cauchy-Schwarz inequality proof for the 3-edge path (can be done in a similar fashion for any tree), let me comment on the authorship of the inequality in question.
In ...

14
votes

Accepted

### Spanning trees: the last darn $1/4$

Consider connected $G$ with $n$ vertices of degree $\ge 3$ and exactly one vertex $v$ of degree 1. Take an extra copy $G'$ of $G$ with $v'$ being its vertex of degree 1.
Now identify $v$ and $v'$ to ...

12
votes

### Embedding of planar graphs

The recent paper below (and its references) may help.
They mention that
every planar graph with max degree $4$ (except for the octahedron) admits
a $2$-bend embedding.
Deciding whether a graph can ...

12
votes

Accepted

### Graph in which no cycle has two crossing chords

Thomassen and Toft [JCTB 31(2):199-224, 1981] showed that any graph with minimum degree at least 3 contains a cycle with two crossing chords from neighbouring vertices on the cycle. The $2n-3$ upper ...

11
votes

Accepted

### The maximum number of edges in an even-cycle-free graph with $n$ vertices

The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. ...

10
votes

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

If $G$ and $H$ are both extremal graphs (possibly for different values of $d$) then their Cartesian product is another extremal graph for the sum of the degrees. So the grid example is just a ...

9
votes

Accepted

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

I hope I am not violating any kind of MathOverflow etiquette by responding to a question 2 years after it has been asked, but your question is answered in the following preprint of mine that just hit ...

9
votes

Accepted

### Bounds for number of edges of a graph, given girth and number of vertices

The bound you quote is actually a little inefficient, because it is harder to find a cycle of fixed length $t$ than to find a cycle of length at most $t$. I recommend that you look at Section 4.1 of ...

8
votes

Accepted

### Smallest Connected Graph for Given Degree Sequence

A theorem of Hakimi says
that any pair of degree-equivalent graphs can be obtained one
from the other by a sequence of "elementary $2$-switchings"
(probably known under many other names), which ...

8
votes

Accepted

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

By Theorem 1 in the paper of Erdős, Kleitman, and Rothschild, the number of triangle-free graphs on $n$ vertices is $2^{n^2(1/4 +o(1)) }$. The number of bipartite graphs with a fixed pair of parts of ...

8
votes

Accepted

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

If you divide the vertex set into 3 parts, A, B and C, with respective sizes $an$, $bn$ and $cn$, and add all the edges except the ones connecting two vertices inside A and a vertex from A and C, then ...

8
votes

Accepted

### Smallest triangle-free graph with chromatic number 5

22 vertices, there are 80 of them.
Jensen and Royle, Small graphs with chromatic number 5 : a computer search
Journal of Graph Theory, 1995.

8
votes

### Population of P people, where each person knows K others, how many people mutually know each other

For $x\geq 2$, and $m$ odd, there is a regular digraph of order $P=(x-1)m$ and of out-valency $K=(x-2)m+\frac{m-1}{2}=\frac{(2x-3)m}{2}-\frac{1}{2}$ with no cliques of size $x$: start with the ...

7
votes

### Are all almost regular graphs obvious?

Don't think just deleting edges from almost regular graph will
result in a regular graph of the same order.
Take $K_{2,3}$. By exhaustive search deleting edges
couldn't find a regular graph on $5$ ...

7
votes

Accepted

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

Lucia's answer given in the linked question from the comment gives an upper bound (i.e., no pair should appear twice as a subset of $A_i$). But of course, the real question starts from here:
When can ...

7
votes

### Removal of non-isomorphic edges results in the same graph

This is essentially a comment on user2097's excellent answer. One consequence of that answer was the construction of a graph with four non-isomorphic edges whose removals result in isomorphic graphs. ...

7
votes

Accepted

### Embedding of planar graphs

Bends are necessary, we have studied this problem in this paper: http://arxiv.org/abs/1009.1315.

7
votes

### The maximal number of copies of a graph $T$ in an $H$-free graph

This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.
It is well-known that a maximal number of edges in a $C_4$-free graph is $\Theta(n^{3/2})$ (since ...

7
votes

Accepted

### Length minimizing graphs between a finite set of points

This is the so-called Steiner Tree Problem.

7
votes

### Graph metric approximating Euclidean metric

Pick some small $\epsilon>0$, take the dilated integer lattice $\epsilon^2\cdot\mathbb{Z}^2$ to be our vertex set, and draw an edge between two vertices if their Euclidean distance is between $\...

7
votes

### Snake algorithm that minimizes straight lines

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because ...

6
votes

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

Let me add a possibly shortest proof of the inequality you asked, although not by Cauchy-Schwarz. Following Sasha's notation, let $g(x)=\int f(x,y) dy$. Then by Holder's inequality,
\begin{align*}
\...

6
votes

Accepted

### A proper definition of connectivity for hypergraphs

Think of the hypergraph as a simplicial complex $\Delta$, with the facets being the hyperedges. Consider property (*) as:
1) The $i$-skeleton of $\Delta$ is full for $0\leq i\leq k-2$ and
2) $\...

6
votes

Accepted

### Existence of connected component with large boundary?

If all degrees are at least 3, there exists a spanning tree with at least $n/4+2$ leaves (D. J. Kleitman and D. B. West, Spanning trees with many leaves, SIAM J. Disc. Math. 4(1991), 99-106), the ...

6
votes

Accepted

### Graph combinatorial optimization problem

The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $...

5
votes

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

This question was recently solved by Balogh & Petrickova. Douglas Zare's bound is tight (apart from the $o(1)$ term). See http://arxiv.org/abs/1409.8123

5
votes

### Removal of non-isomorphic edges results in the same graph

Not an answer, just an extended comment.
For $n \leq 10$ such graph does not exists.
I am currently checking $n = 11.$ Are there any structural properties that such a graph has, other than it is ...

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

#### Related Tags

extremal-graph-theory × 186graph-theory × 155

co.combinatorics × 109

extremal-combinatorics × 25

graph-colorings × 20

reference-request × 14

combinatorial-optimization × 11

ramsey-theory × 8

spectral-graph-theory × 7

random-graphs × 7

algorithms × 6

bipartite-graphs × 6

matching-theory × 5

trees × 4

matrices × 3

open-problems × 3

hypergraph × 3

hamiltonian-graphs × 3

cycles × 3

pr.probability × 2

mg.metric-geometry × 2

inequalities × 2

directed-graphs × 2

graph-minors × 2

topological-graph-theory × 2