MathDB

Given is a graph

G

. An empty subgraph of

G

is a subgraph of

G

with no edges between its vertices. An edge of

G

is called important if and only if the removal of this edge will increase the size of the maximal empty subgraph. Suppose that two important edges in

G

have a common endpoint. Prove there exists a cycle of odd length in

G

Problem Statement