# Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

345 questions
Filter by
Sorted by
Tagged with
93 views

### Maximal vertices of a connected k-regular bipartite graph

Call a graph "$k$-special" if it is a connected $k$-regular bipartite graph such that if $AB$ and $AC$ are edges, then there exists exactly one other vertex $D$ such that $BD$ and $CD$ are ...
• 33
113 views

### A generalization of Turan's theorem

The Turan's theorem gives a tight upper bound of the number of edges in a $K_n$-free graph. I didn't manage to find some information about the generalization of this theorem when we're asked to ...
• 1,667
135 views

### Showing graphs with more than $\lfloor\frac{n^2}{4}\rfloor$ edges have a $3$-cycle.

From "A Brief Introduction to Spectral Graph Theory" Exercise 1.2 states A graph on $n$ vertices that contains no 3-cycles has at most $\lfloor \frac{n^2}{4}\rfloor$ edges. My thought ...
• 3,074
31 views

### Size of a minimal vertex cover as an expression in terms of vertices and edges

I am currently working on the following problem: Let $\tau(G)$ be the minimum size of a vertex cover of a graph $G=(V,E)$. Show that for $|V|=n$, $|E|=m$, we have $$\tau(G)\leq\frac{2mn}{2m+n}$$ I am ...
• 59
50 views

### Making a Star Graph Claw-Free: Edge Addition Count

Let $S_{n}$ be a star with $n$ vertices; see Star graph. $S_4$ is called a claw. A claw-free graph is a graph in which no induced subgraph is a claw. My question is: starting from a star graph $S_n$, ...
• 2,216
64 views

### Proof that the maximum number of edges of a 1-planar graph is 4n - 8

The Wikipedia article about 1-planar graphs says that the maximum number of edges in such graphs is $4n - 8$ Every 1-planar graph with n vertices has at most 4n − 8 edges.[4] More strongly, each 1-...
1 vote
75 views

• 23
71 views

### In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.

I have been trying to solve this question, it was already asked but the response seems to have some issues. The accepted answer implies that if a graph has a cycle of length 4, this implies that it ...
• 115
1 vote
37 views

• 6,670
10 views

• 2,216
1 vote
57 views

### Maximum number of edges in a Line Graph L(G)

The line graph 𝐿(𝐺) of a simple graph 𝐺 is defined as follows: There is exactly one vertex 𝑣(𝑒) in 𝐿(𝐺) for each edge 𝑒 in 𝐺. That being said, how can I prove that the maximum number of edges ...
58 views

### Lower bound for couples of disjoint sets in some partitions of the power set

Now crossposted at Mathoverflow. Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n]) \setminus \{\emptyset\}$. ...
• 2,545
95 views

### Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$ For given integers $d>0$, $k>1$ ...
• 3,251
111 views

### Maximum number of vertices with degree three in maximal bipartite planar graphs

A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
• 2,216
223 views

### Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory". 6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
• 2,216
17 views

### Maximal planar graphs with minimum independent sets

The lower bound is known to follow immediately from the Four Color Theorem. Theorem 1. If $G$ is a planar graph with order $n$, then $\alpha(G) \geq \frac{n}{4}$. The lower bound in Theorem 1 is sharp....
• 2,216
7 views

### What's the $p$-th power of a $k$-uniform tight cycle?

I understand that in a graph when there's a cycle, the $p$-th power of the cycle is when all vertices at a distance of at most $p$ from each other (on the base cycle) are joined with edges. A $k$-...
• 811
1 vote
31 views

• 335
1 vote
59 views

### Triangle-free graphs on a set $V$ of $n$ labeled vertices

Prove that the number of triangle-free graphs on a set $V$ of $n$ labeled vertices is $2^{(\frac{1}{4} + o(1))n^2}$ where the $o(1)$ term tends to $0$ as $n \to \infty$. I have a few ideas, but not ...
• 335
44 views

### Find (with proof) the smallest 3-regular simple graph G with κ(G) = 1.

So, my approach involves taking a star graph of order 3, and then taking considering the vertex in the middle to be the cut-vertex. Consequently, I cultivate the graph with 2 components in mind, the ...
34 views

### Question about "growing layers of a planar graphs"

Given a planar graph $G$ k nodes $S$ of $G$ construct "layers" $L_i$ for $i=0,1,...$ as follows $L_0=S$, having constructed layers $L_0,L_1,..,L_i$ layer $L_{i+1}$ consists of those nodes ...
• 288
142 views

### Seeking proof that the greedy algorithm is in fact the most optimal algorithm to construct graph with maximum variance in its degree distribution.

User inputs: number of nodes (n) and number of links (k). Objective: create an undirected (n,k) graph without multi-edges and without self loops that exhibits the maximum standard deviation in its ...
250 views

### Upper bound of graph diameter, using only degree of vertices

Let $G$ be a connected graph with $n$ vertices, and the degree of its vertices are $d_1,...,d_n$. I want to find an upper bound on the diameter of $G$, using only $n,d_1,...,d_n$. One result I know is ...
• 117