The study of maximal or minimal graphs satisfying certain properties.

learn more… | top users | synonyms

2
votes
2answers
32 views

Deriving the number of edges in a Turán graph

When stating Turán's theorem, the Turán graphs are often used to give an upper bound on the possible number of edges in a graph without a clique of a certain size. This bound can also be proven ...
0
votes
0answers
28 views

Why functions derivitive crosses x axis, where function does not have an extreme point?

My function: $(x+0.4)^2-\cos\left(1+\frac{\cos(x/2)}{\sin(x/2)}\right)$ My derived function: $0.8+2x+\frac{1}{2}\frac{1}{\sin(x/2)^2}\sin\left(1+\frac{\cos(x/2)}{\sin(x/2)}\right)$ Where $x$ is very ...
0
votes
0answers
4 views

Family of graphs with structural intersection (namely, no isolated vertices)

In the book Extremal Combinatorics: With Applications in Computer Science I found the following theorem: Theorem. Suppose that $\mathcal{F}$ is a family of (labeled) subgraphs of $K_n$ such that for ...
0
votes
0answers
17 views

About Proof by extremality

Can someone explain the basic idea behind proof by extremality in simple language? Like in proof by contradiction, for $P \rightarrow Q$, we assume $P$ and not $Q$ and show they cannot happen ...
0
votes
0answers
29 views

Erdős-Sós conjecture tightest upper bound

The Erdős-Sós conjecture states that any graph of average degree greater than or equal to $k-2$ contains a copy of any tree on $k$ vertices. Does anyone know the current best upper bound on the ...
1
vote
1answer
44 views

Turan's theorem - maximum number of edges.

Question: 30 people need to place a call to each other using their cellular phones (one call per each pair). A cellular phone company gets 1 $ for each call between two people at distance between 800 ...
0
votes
1answer
71 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
4
votes
1answer
88 views

Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$

Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $deg(u) + deg(v)\leq 13$. Furthermore, there exists an example showing that 13 cannot be replaced by ...
1
vote
1answer
32 views

Do complete graphs maximize the number of triangles?

Let $G$ be a graph with $a\choose 2$ edges (and an arbitrary number of vertices). Is it true that it has at most $a\choose 3$ triangles? Context: this continues the question Number of triangles in a ...
2
votes
2answers
57 views

Graph containing every trees of size $n$ as subgraphs

What is the minimum number of edges of graph $G$, so that every tree of size $n$ is a subgraph of $G$? I personally managed to find a lower bound of $c n \log n $ and an upper bound of $C n \log ...
3
votes
1answer
64 views

Definition of compatible vertices

I'm reading the Extremal Graph Theory book by Bollobás, and I'm stuck at the definition of 'compatible vertices'. It's here at the bottom of p.13 It says : "Call two vertices compatible if every ...
1
vote
0answers
31 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...