# Tag Info

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

### 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 ...
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 ...
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$. ...

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

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

### 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$ ...
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 ...

### 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. ...
Accepted

### Embedding of planar graphs

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

### 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 ...
Accepted

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

This is the so-called Steiner Tree Problem.

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