Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

0
votes
1answer
23 views

Find minimal set of edges in k-partite graph that every k-clique has an edge from this set.

There is given $k$-partite graph $G$, where independent sets have following cardinalities: $n_{1},n_{2},...,n_{k}$ We say that $k$-clique is marked if has at least one edge from given set of edges $A$....
1
vote
0answers
27 views

Using extremal graph theory theorem to prove a theorem in planar graphs

We have, by one of Turán's theorem, that among the $n$-vertex simple graphs with no $r+1$ clique, the complete $r$-partite graph which has its number of vertices in each partite sets differing by at ...
3
votes
1answer
33 views

If $G$ is any n-vertex triangle free graph not containing a copy of $D_d$, then $e(G) \leq n(d-1)$

when revising for an upcoming exam on Graph Theory I came across the problem above. This was the last part to a question on Extremal Graph Theory, and in the previous parts, the question covered the ...
0
votes
0answers
23 views

The disjoint cliques problem for complete graphs. [duplicate]

There is complete graph $K_{n}$ Find formula for maksimal number of disjoint to each other $k$-cliques in $K_{n}$. Let denote it as $A(n,k)$ I did some research and i computed a formula: $B(n,k)=\...
0
votes
0answers
15 views

Turan density results for 4- or 5- graphs

I was wondering if there are results for Turan densities of 4- or 5-graphs (hypergraphs). I am aware of several surveys of hypergraph Turan densities (due to Pikhurko, Keevash), but these mainly focus ...
1
vote
1answer
61 views

Problem on graphs with more edge than a Turan number

I ran into the following problem when revising for a Graph Theory exam - I had already solved part c) however I am keeping it in as it seems to link to part d). Now I see these type of problems on ...
1
vote
0answers
32 views

Maximum number of triangles given fixed number of edges

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $O(E^{1.5})$ and the maximum occurs with it’s a clique. Now my ...
0
votes
0answers
21 views

Minimum path distance from a source

Suppose I have a path-connected subset $I$ of $\mathbb{R}^n$ (not convex, but can be contained in a product of finite-measure closed intervals), and I define a "source point" $a \in \mathbb{R}^n$. ...
-1
votes
1answer
185 views

Optimization problem for routes

Let a group of farms each have a p-letter name. No two farms have the same name, however, and they all only consist of x's and z's. For example, if p=2, then xx, zz, xz, zx are the farms in the state. ...
1
vote
0answers
11 views

Do strongly regular graphs maximize spectral gaps?

Across the set of d-regular n-vertex graphs, if there is a strongly regular graph in that set, it often (always, as far as I was able to check) seems to maximize the spectral gap: $\lambda_1 - \...
0
votes
1answer
28 views

Local minimum of the difference of two functions

Consider the function $$u(x)=\begin{cases}x \qquad \qquad x\in[0,\frac{1}{2}]\\-x+1 \qquad x \in[\frac{1}{2},1]\end{cases}.$$ Certainly $u$ is continuous in $[0,1]$, derivable at each point except at ...
6
votes
1answer
83 views

Dominating sets in tournaments; is $2^{n+1}-2$ tight?

A tournement is a directed graph such that for every pair of distinct vertices $\{x,y\}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$x\to y$" to mean "there ...
3
votes
0answers
112 views

$n$ vertex graph with more edges than its Turan number: $e(G) = t_r(n) + 1$

I have been struggling with this problem for quite some time now and I cannot think of a way to proceed with either part: Suppose that G is a graph with $n > r + 1$ vertices and $t_r(n) + 1$ edges:...
4
votes
2answers
108 views

Calculate the maximum number of edges of a graph without two disjoint $K_3$

Let $G$ be a simple graph without two disjoint $K_3$ (no common vertices). What is the maximum of $|E(G)|$ in terms of the number of vertices $n$ of $G$? If $G$ is a graph without a $ K_3$ , I get ...
0
votes
0answers
12 views

How can dividing the graph into k-1 subsets guarantee that a clique on k vertices is avoided ?

Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
3
votes
2answers
53 views

tree has exactly $k$ nodes with degree $4$. Show that this tree has $2k+2$ leaves.

Prove: If a tree has exactly $k \geq 1 $ nodes with degree $4$, then this tree has at least $2k +2 $ leaves. ( nodes with degree $< 4 $ are only allowed for the leaves ). So I think that we can ...
1
vote
0answers
22 views

How to interpret a limit in a graph theory result

The following is a theorem in the linked paper here. To add some context, the authors also state: Throughout this paper...$t^k$, the average degree, will always be an increasing function of $...
1
vote
1answer
60 views

Number of edges in Turán graph

I am trying to prove that the number of edges in the Turán graph $T^r(n)$ (that is, the complete $r$-partite graph on $n$ vertices whose partition sets differ in size by at most 1) satisfy the ...
1
vote
1answer
44 views

How can I get maximum number of vertices if I already know edges

If I already know edges how can I get the maximum number of vertices? Question: There is a graph that has $36$ edges, and where every vertex has degree at least $5$. What is the maximum number of ...
0
votes
0answers
26 views

Theorem in graph theory about crossing numbers of $C_4 \times C_4$ graph

Consider first these definitions Definition $1$. A drawing of a graph $G$ is optimal if it has the minimal number of possible crossings Definition $2$. For a subset $X$ of vertices of a graph $G$, ...
0
votes
2answers
61 views

Prove that a graph on $n$ vertices which not contains $K_4$ as a subgraph has at most $\frac{n^2}{3}$ edges.

Prove that a graph on $n$ vertices which not contains $K_4$ as a subgraph has at most $\frac{n^2}{3}$ edges. I tried prove that with induction. I assume for graph with $n-1$ vertices that has at most ...
3
votes
0answers
61 views

Hamiltonian cycle containing each edges of graph

Let $n$ be the number of the vertices of a graph $G$. If the degree of each vertex of $G$ is at least $\frac{n+1}{2}$, prove that for an edge $e$ of $G$ there is a Hamiltonian cycle containing $e$. ...
1
vote
0answers
36 views

Weaker Version Of Hadwiger's Conjecture

Hadwiger's Conjecture states that if we have a graph $G$ with chromatic number $k$, then $G$ contains $K_k$ as a minor. My question is, is it already known that there is some finite list of graphs $\...
1
vote
1answer
28 views

On properties of extremal graphs

Let H be a graph, and define $c_n(H) := \frac{ex(n, H)}{\frac{n(n-1)}{2}}$ Prove that $c_n(H) \leq c_{n−1}(H)$, and show that $\lim_{n→∞} c_n(H)$ exists. So first of all, if we managed to show that ...
1
vote
0answers
27 views

Materials to read for Graph Theory.

I am interested in graph theory and currently finished learning the basic knowledge in graph theory. Before I continue on to study the following three branch of graph theory, namely Topological Graph ...
1
vote
1answer
24 views

Show that the limit of the density of the Turán graph T(r,n) is 1-1/r+O(1).

Some notes I have claim that as n tends to infinity the density of the Turán graph T(r,n) tends to 1-1/r+O(1). How can this be shown?
2
votes
1answer
105 views

There is two triangles with common edge in graph $\Gamma$

Let $\Gamma$ be a graph with $2n$ vertices and $n^2+1$ edges. Than there is two subgraphs $K', K'' \subset \Gamma$ both isomorphic to $K_3$ such that they have a common edge. I have tried to count ...
2
votes
1answer
69 views

Help with induction for graph with no path of length $k$

I am asked to show that if a graph $G$ of order $n$ does not contain a path of length $1\leq k \leq n$, then $G$ has at most $\frac{n(k-1)}{2}$ edges, which can happen iff $k\mid n$ and $G$ is the ...
2
votes
1answer
245 views

Lower bound for the Ramsey number $R(3,t)$

Define the Ramsey number $R(s,t)$ to be: $\text{min}\{n \in \mathbb N \mid \text{colouring } E(K_n) \text{ blue and yellow yields a blue } K_s \text{ or a yellow } K_t\}$ Then I am asked to find that ...
2
votes
1answer
77 views

Extremal graphs definition

I'm trying to understand extremal graph theory using Diestel's book. I have two problems in it's introduction. First the definition of extremality for graph $H$ and $n$ vertices is somewhat confusing. ...
2
votes
1answer
16 views

projecting antichains to middlemost levels

Suppose I have an antichain $A\subset \mathcal{P}(n)$ such that $x\in A\Rightarrow |x|\leq k\leq n/2$. Is there a nice way to "project" my antichain to the middle level? I guess I'm looking for ...
2
votes
0answers
70 views

Extremal graph without cycle length $k$ or longer.

When $k\geq 3$, denote $\mathcal{C}_{k}=\left\{C_{n}\mid n\geq k\right\}$ the family of cycles of graph. I am trying to find ${\rm{ex}}\left(n;\mathcal{C}_{k}\right)$ and ${\rm{EX}}\left(n;\mathcal{C}...
1
vote
1answer
46 views

How sparse is a graph of bounded treewidth?

I often see references to treewidth being a measure of sparseness, but is there a known bound? More exactly, given a graph $G$ with $n$ vertices and treewidth at most $k$, is there a function of $n$ ...
0
votes
0answers
27 views

Extremal combinatorics problem on graph matching

Let $A$ and $B$ be two disjoint set of vertices. Let $\{M_i\}_1^n$ be $n$ edge-disjoint matchings from $A$ to $B$. Let $G$ be the graph with $V = A \cup B$ and $E = \cup_{i} M_i$. Assume that for ...
1
vote
2answers
33 views

Given a graph with n vertices, if it have more than $\frac{nt}{2}$ edges then there exists a simple path of length $t+1$.

I have been working on this problem for a while, and yet I do not have a clear lead. Currently all I have is that the average degree is greater than $t$ so exists a vertex with degree at least $t+1$, ...
6
votes
1answer
150 views

$6$-regular graph of order $25$ and diameter $2$

Is there a $6$-regular graph of order $25$ and diameter $2$? According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $n\leq r^2+1$. When ...
0
votes
0answers
136 views

Characteristic polynomial of the path graph

My question is about How to do prove path graph $$Φ(P_n,x)=Π(x-2\cos(2πi/(n+1))$$
0
votes
2answers
76 views

Discrete Maths: Graphs

Show that if there is no cycle of length 4 in graph with 10 vertices then it has at most 27 edges. I have no clue how to do this task.
0
votes
1answer
74 views

Distinguishing vertex, edge, and edge-contraction critical graphs

A finite, simple, undirected graph $G=(V,E)$ is said to be vertex-critical if for all $v\in V$ we have $\chi(G\setminus \{v\}) < \chi(G)$. Similarly, we call it edge critical, if removing any edge ...
1
vote
1answer
217 views

Graphs: Minimum Cycle Basis generated by Horton's algorithm is not consistent

This is my first post. I've a big doubt regarding Graphs, I'm working on a program to generate them using different efficient algorithms, starting from "Horton" (1978, 1st polynomial time approach). ...
3
votes
1answer
150 views

Find the smallest number of edges that a 3-regular graph of girth 4 can have

I know the girth of a graph $G$ is the size of a smallest cycle in $G$. I'm trying to find a formula for how many edges in terms of $n$. I've just been playing around with examples and think a ...
0
votes
1answer
33 views

Extremal graph in euclidean space

Let $x_1,x_2,\dots,x_n$ be vectors of unit norm in a Euclidean space. Show that the number of unordered pairs $(i,j)$ for which $|x_i + x_j| < 1$ is at most $\lfloor{n^2\over4}\rfloor$ A hint to ...
7
votes
2answers
157 views

Maximum number of edges in a graph where length of every cycle is a multiple of 3

I am doing a problem which asks to find the maximum number of edges in a graph on $n$ vertices which has the property that every cycle's length is a multiple of 3. I was able to show that if $G$ ...
1
vote
0answers
26 views

H is a cycle with an extra chord. $(A,B)$ be a partition of $V(H)$. Then unless H is bipartite, $H$ contains paths of every length

Let H be a cycle with an extra chord. Let $(A,B)$ be a nontrival partition of $V(H)$. Then unless H is bipartite between $A$ and $B$, $H$ contains paths of every length $l$ $\lt$ $|V(H)|$ which begin ...
2
votes
1answer
49 views

Problem on Extremal Graphs: three independent paths

The problem states that: A simple (or strict) graph with $n$ vertices and $m>\dfrac{3(n-1)}{2}$ edges, has two vertex joined by three independent paths. Any hints, ideas or useful results, to ...
0
votes
1answer
69 views

Is the complete graph $K_n$ $n-1$-connected?

Is the complete graph $K_n$ $n-1$-connected? I'm trying to have a better understanding of k-connectedness and it helps to look at an extreme case. My intuition is that it's either that or it's 1-...
4
votes
1answer
99 views

Dense triangle free graphs with paths of length 3 between every pair of vertices

Does there exist an infinite family of dense (i.e. #edges = $m = O(n^2)$) graphs such that they are triangle-free and have a path of length exactly 3 between every pair of vertices? Best lower bound(...
1
vote
1answer
448 views

Maximum independence number of any $d$-regular graph on $v$ vertices

What I seek is a formula $F(v,d)=M_v$, where $v$ is the number of vertices in a group and $d\leq v-1$ is the degree that they ALL have to be ($d$-regular graph$^{\dagger}$), which finds the MAXIMUM ...
2
votes
1answer
67 views

Minimal number of edges in a 4 connected graph

For $n\ge 5$, what is the minimal number of edges of a $4$-connected graph on $n$ vertices? (denote this number by $j(n)$). All I could establish is $j(n) \ge 2n$ as for each connected graph $G$, $...
5
votes
0answers
108 views

Minimum Number of People Such That No Two People Know the Same Two People

In a population of $n$ people, each person knows $k$ other people and if person A knows person B then person B knows person A. However, no two people, A and C, know the same two people B and D. What ...