# Tag Info

• 28.7k
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 ...
• 33.6k

### 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 ...
• 144k
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 ...
• 1,092
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$. ...
• 28.7k

### 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 ...
• 18.2k
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 ...
• 736
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 ...
• 144k
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 ...
• 27.1k
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 ...
• 17.1k
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.
• 10.8k

### 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 ...
• 2,711

### 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$ ...
• 23.3k
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 ...
• 3,602

### 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.
• 17.1k

### 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 ...
• 18.6k
Accepted

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

This is the so-called Steiner Tree Problem.
• 93.7k

• 29.6k
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 ...
• 86.7k