# Decomposing a complete graph to avoid small odd cycles

Home

Search

Subjects

About Erdös

About This Site

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

It is known that a complete graph on \(2^n\) vertices can be edge-partitioned into \(n\) bipartite graphs (and this is not true for \(2^n+1\)). Suppose a complete graph on \(2^n+1\) vertices is decomposed into \(n\) subgraphs. Let \(f(n)\) denote the smallest integer \(m\) such that one of the subgraphs must contain an odd cycle of length less than or equal to \(m\).

# Problem (proposed by Erdös and Graham [1])

Determine \(f(n)\).# Problem (proposed by Erdös and Graham [1])

Is \(f(n)\) unbounded as \(n \rightarrow \infty\)?Although this is a fairly old problem, relatively little is known. It can be easily shown that \( C_5\) and \( C_7\) can be avoided provided \( n\) is large.