# Questions tagged [forbidden-subgraphs]

For questions related to graphs which do not contain any element of a family of graphs as a subgraph. E.g., Kuratowski characterized *planar graphs* as those which do not have either a subdivision of the complete graph K_5 on five vertices or a subdivision of the complete bipartite graph K_{3,3} as a subgraph.

7 questions
Filter by
Sorted by
Tagged with
31 views

### What is the fewest vertices a non-planar subgraph of the Knight's graph can have?

I was wondering about the title question: What is the fewest vertices a non-planar subgraph of the Knight's graph can have? I have found a subgraph with 14 10 vertices that is non-planar And it ...
17 views

### Extremal graphs for paths of fixed length

One can show that if $G$ is a graph on $n$ vertices and does not contain a path (cycles do not count) of length $k$, then $e(G) \leq \frac{k-1}{2}n$ (by induction - remove a vertex of minimal degree ...
### Forbidden $K_4$ in a subgraph of $K_{10}(n)$
In terms of $n\geq 1$, find the maximum possible number of edges in a subgraph $H$ of $K_{10}(n)$, the complete $10$-partite graph with $n$ vertices in each class, containing no copy of $K_4$. It is ...