Even circuit theorem
id:
even-circuit-theorem-199-6192224
title:
Even circuit theorem
text:
In extremal graph theory, the even circuit theorem is a result of Paul Erdős according to which an n-vertex graph that does not have a simple cycle of length 2k can only have O(n1 + 1/k) edges. For instance, 4-cycle-free graphs have O(n3/2) edges, 6-cycle-free graphs have O(n4/3) edges, etc.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Even_circuit_theorem
date created:
date modified:
2022-10-24T07:16:25Z
main entity:
{"identifier":"Q25304324","url":"https://www.wikidata.org/entity/Q25304324"}
image:
fields total:
13
integrity:
13