The study of maximal or minimal graphs satisfying certain properties.

learn more… | top users | synonyms

0
votes
2answers
50 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
0
votes
1answer
16 views

Can a chord determine two fundamental circuits in a graph

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph ...
0
votes
0answers
29 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...
0
votes
1answer
16 views

Why does $K_{\chi(H)}(|H|)$ contain the graph H?

Why does $K_{\chi(H)}(|H|)$ necessarily contain the graph H? This is part of the more general question as to why $K_{\chi(H)}(t)$ should contain H for sufficiently large t. Here $K_{r}(t)$ is a ...
0
votes
0answers
19 views

Determine the value of $ex(n,P_4)$

I want to determine the exact value of $ex(n,P_4)$ I believe that the answer to this is $n$, if $n\equiv 0$ (mod $3$), and $n-1$ otherwise. Given n vertices, one can create multiples of $K_3$. If ...
2
votes
2answers
52 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
31 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
5 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
18 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
34 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
52 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.
5
votes
1answer
104 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
60 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
69 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
32 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 ...