The study of maximal or minimal graphs satisfying certain properties.

learn more… | top users | synonyms

5
votes
2answers
52 views

21 points on circumference of a circle must have at least 100 pairs separated by 120+ degrees.

Prove that at least 100 of the arcs determined by the pairs of these points subtend an angle not exceeding 120 degrees at the center. How do I prove this? Induction? Help please. Thanks.
1
vote
2answers
51 views

Probability spaces over graphs: which area has focus on them?

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and ...
0
votes
1answer
18 views

Conditional Extreme. Find a point in $\mathbb{R^2}$ that has the smallest sum of squared distances from the lines $x=0,y=0, x-y+1=0.$

I can find the main function, but I do not know the condition, to set up the Lagrange equation. Can anyone see, what condition the point has to satisfy here?(So as to apply the Lagrange multiplier ...
0
votes
1answer
20 views

With the given point $M(a,b,c)$ in $\mathbb R^3$, find the tetrahedron with the smallest volume that is formed with a plane that..

With the given point $M(a,b,c)$ in $\mathbb R^3$, find the tetrahedron with the smallest volume that is formed with a plane that contains $M$ and who's points are the intersections of that plane with ...
0
votes
2answers
41 views

Finding the point on the parabola closest to a point

Find the point on the parabola $ 2x - 2y^2 = 7$ which is closest to the point $ (4,16) $. I've tried the distance $ D $ between the point $ (x,y) $ and $ (4,16) $, then the problem is simplified by ...
2
votes
1answer
33 views

Where does the “Zarankiewicz's lemma” from?

In order to prove Turan's Theorem, someone introduced a lemma so called "Zarankiewicz's lemma": If $G$ is a $k$-free graph, then there exists a vertex having degree at most $\displaystyle \lfloor ...
1
vote
0answers
8 views

Cutting a colour-critical indecomposable graph

Let $G=(V,E)$ be an arbitrary indecomposable k-colour-critical graph ($k\geq4$). Is it in general possible to find a cut $C=(S,T)$, such that $S$ is a $k-1$-chromatic graph and $T$ is the complete ...
1
vote
1answer
31 views

Finding the local extremes of this implicitly given function.

$$x^2+y^2+z^2-xz-yz-2x+2y-2=0. $$ So I have $$F(x,y,z)=x^2+y^2+z^2-xz-yz-2x+2y-2 \\ \frac{\partial F}{\partial z}=2z-x-y\neq 0 \\ \frac{\frac{\partial F}{\partial ...
2
votes
1answer
42 views

Inside an elliptical paraboloid with an equation $z=\frac{x^2}{a^2}+ \frac{y^2}{b^2}$ bounded by $z=h$ draw an right-angle parallelepiped..

Inside an elliptical paraboloid with an equation $z=\frac{x^2}{a^2}+ \frac{y^2}{b^2}$ bounded by $z=h$ draw an right-angle parallelepiped.. with the largest possible volume. What confuses my most is ...
1
vote
1answer
33 views

Family functions of derivatives and extremum values. [closed]

Explore the family of functions $ f(x) = x^3 + kx + 1 $ where $ k $ is a real constant. How many and what type of local extrema are there? Your answer should depend on the value of $ k $, that is, ...
0
votes
1answer
64 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
2
votes
1answer
61 views

Inside a circle of radius $r$ insert a triangle with the largest possible area.

I thought I could use this $r$, being the circumradius of the triangle, thereby the area being: $\frac{abc}{4r}$. Now from here I need to find a,b,c so the area is maximal. Could I do this with ...
0
votes
0answers
26 views

Inductive proof of Turan's theorem

I am trying to use induction to show that the maximum number of edges in a graph with $n$ vertices and no $k+1$ clique is \begin{align} (1- \frac{1}{k})\frac{n^2}{2} \end{align} and the unique graph ...
0
votes
0answers
24 views

Graph containing every tree

Let $G$ be a graph on $n$ vertices of size at least $(k-1)n - {k\choose 2} +1$. Show that $G$ contains all trees of order $k+1$. What I really would like to show is that there is a subgraph of ...
0
votes
1answer
19 views

Unique Extremal Non-Hamiltonian Graph

Let $G$ be a graph on $n$ vertices with size at least ${n\choose 2} - (n-2)$. Show that $G$ is Hamiltonian. What is the unique Extremal graph? The first part I did. I even know the Extremal graph ...
0
votes
1answer
25 views

Lower bound for monochromatic triangles on 2 coloring of $K_n$

I am trying to show that there is at least $\frac{n(n-1)(n-5)}{24}$ monochromatic triangles in any 2 coloring of the edges of $K_n$. I am trying to show this using Mantel's theorem but I can't seem ...
2
votes
0answers
27 views

Prove the equivalence of Szemeredi’s regularity lemma

In my textbook, Szemeredi’s regularity lemma states as $\forall\epsilon>0,\forall$ integer $m$ $\exists$ integer $M$ $\forall$ graph $G$ on $n\ge m$ vertices $\exists k$ with $m\le k\le M$ and an ...
1
vote
0answers
121 views

$(r+1)$ Clique of Induced subgraph and Turan’s theorem

$G$ is a $s$ regular graph. $A$ is a set of vertices where $|A| = s$ and $A \subseteq G$. $E$ is the number of edges of $G$. $n$ is the total number of vertices of $G$. Problem: Find the lower ...
0
votes
0answers
39 views

Deleting tree from graph with large average degree will raise chromatic number

I am trying to bite problem 7.17 in Diestel graph theory book: 7.17 Can large average degree force the chromatic number up if we exclude some tree as an induced subgraph? The hint is: Consider ...
4
votes
1answer
88 views

Minimum number of edges such that $\chi_1=\chi$

Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
1
vote
1answer
31 views

By adding $k$ edges to a $K_r$-free graph, what is the maximum clique number attainable?

Denote by $\omega(G)$ the size of a maximum clique of a graph $G$. Suppose $G$ is a $K_r$-free graph (i.e. $\omega(G) < r$), and let $G'$ be a graph obtained by adding at most $k$ edges to $G$. ...
1
vote
0answers
29 views

Good embeddings for degree-diameter graphs

I've put together a degree-diameter notebook for various graphs of the degree diameter problem. My favorite table is at The (Degree,Diameter) Problem for Graphs. Here are sample edge lists without ...
0
votes
2answers
29 views

To find a extremal point of a function with parameters

I have a function $$f(x) = (x-5m)(x+m)^2$$ I have tried to find the extremal points of this function (and then find if it's local maxima or minima). That means I need to find the x of derivative. The ...
2
votes
0answers
43 views

Turan's theorem for balanced r-partite graphs

I'm curious about the following restricted version of Turan's theorem: Among all $r$-partite graphs that are balanced (exactly $n/r$ nodes per part), what is the maximum size of a graph with no ...
2
votes
1answer
30 views

On bounding the diameter of a undirected simple connected graph

This may be a something already there in literature but I am unable find it: Given an undirected simple connected graph $G$ whose vertices has a degree at-least $d$ and $\ge c n^2 $ edges, where $0 ...
1
vote
2answers
241 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
44 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
32 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
17 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 ...
2
votes
2answers
327 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
43 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
2answers
39 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 ...
1
vote
1answer
177 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
190 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
37 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
68 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
162 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
33 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 ...