# Questions tagged [extremal-graph-theory]

Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.

**4**

**2**answers

### The number of monochromatic triangles

**9**

**1**answer

### Conjecture on minimum size of graph

**0**

**0**answers

### maximum radius for a $k$-set of vertices in a graph

**4**

**3**answers

### How to show that random graphs cannot be embedded with short edges

**0**

**0**answers

### (Weakly) connected sets with large (out-)boundary

**2**

**1**answer

### Combinatorial process on multisets of integers

**2**

**0**answers

### What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph

**2**

**0**answers

### Expectation of Hadwiger number of a random graph

**1**

**0**answers

### Expected value of the difference of the Hadwiger number and the chromatic number

**6**

**2**answers

### Snake algorithm that minimizes straight lines

**3**

**1**answer

### Minimum size of regular graph with no short cycles

**13**

**2**answers

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

**1**

**0**answers

### Number of maximum matchings in bipartite graphs of positive surplus

**17**

**3**answers

### Graph that minimizes the number of b/w colorings where white vertices have an odd number of black

**2**

**1**answer

### Smallest size of graph covered by infinite tree

**0**

**1**answer

### Making graphs isomorphic with edge additions/removals

**14**

**1**answer

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

**7**

**0**answers

### Szemerédi's regularity lemma for binary operations

**9**

**0**answers

### Largest number of simple paths between two vertices

**3**

**1**answer

### Independence number of $C_4$-free graphs

**3**

**0**answers

### Connected set of vertices having large boundary in a subset?

**3**

**0**answers

### Boundary differences in two graphs

**2**

**0**answers

### Existence of a subcover with large boundary

**2**

**0**answers

### Do sparse graphs contain a single regular pair?

**4**

**0**answers

### Maximal number of smallest circuits in a matroid

**0**

**1**answer

### Matching book thickness of the wheel graph $W_n$

**2**

**2**answers

### Existence of connected component with large boundary?

**1**

**0**answers

### 4-cycles vs eigenvalue information on quasi-random graphs

**8**

**2**answers

### Graph metric approximating Euclidean metric

**4**

**0**answers

### Expected number of bridges in a random subgraph

**8**

**1**answer

### Sum of degree differences for simple graphs

**1**

**1**answer

### Density of bipartite $d$-degenerate graph

**1**

**0**answers

### At what aspect ratio does the Ruzsa-Szemeredi Theorem begin?

**0**

**1**answer

### Matching book embedding of Cartesian products of graphs

**4**

**2**answers

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

**3**

**0**answers

### The pagenumber of subdivision of a complete graph

**2**

**1**answer

### A simple equality for book embedding of two graphs

**6**

**2**answers

### Lovasz local lemma for the edge model

**2**

**0**answers

### How many edges can be in an unbalanced bipartite graph of girth $>6$?

**4**

**0**answers

### Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?

**4**

**0**answers

### Faithful Orthogonality Dimension of Kneser Graphs

**7**

**1**answer

### Chromatic number of $C_4$-free graphs

**3**

**1**answer

### Counting the forests obtainable by removing subtrees from binary trees

**2**

**1**answer

### Combinatorial optimization for a sequential random process on graphs

**0**

**0**answers

### Properties of the collection of maximal independent sets of a graph

**7**

**1**answer

### A proper definition of connectivity for hypergraphs

**3**

**1**answer

### The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles

**3**

**1**answer

### How many graphs of order n, maximum degree k, and maximum diameter d exist?

**5**

**1**answer

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

**-1**

**1**answer