# Tagged Questions

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.

778 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 ...
1k 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 ...
974 views

### 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". http://www.math.ucsd.edu/~erdosproblems/erdos/...
864 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 ...
953 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. ...
914 views

81 views

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

In reading a paper, I came across an affirmation "a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" In a previous question I asked in this site about it, I was reffered to a ...
300 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, ...