Show that every graph $G$ has an edge cut $[X,Y]$ such that $G[X]$ and $G[Y]$ are even.
时间: 2024-01-01 19:03:35 浏览: 22
We will prove the statement by induction on the number of edges in the graph.
For the base case of $|E(G)|=0$, the graph has no edges and we can choose any partition $X$ and $Y$ such that $G[X]$ and $G[Y]$ are both empty. Then $G[X]$ and $G[Y]$ are both even.
For the inductive step, assume that the statement is true for all graphs with fewer edges than $G$. Let $e=uv$ be any edge in $G$. By the inductive hypothesis, there exists an edge cut $[X',Y']$ of $G-e$ such that $G-e[X']$ and $G-e[Y']$ are both even.
Now consider two cases:
Case 1: $u$ and $v$ are in different components of $G-e$. In this case, we can let $X=X'$ and $Y=Y'$, and we have that $G[X]$ and $G[Y]$ are both even.
Case 2: $u$ and $v$ are in the same component of $G-e$. Let $X=X'$ and $Y=Y' \cup \{u,v\}$. Then $G[X]$ is even because $G-e[X']$ is even, and $G[Y]$ is even because $G-e[Y']$ is even and $u$ and $v$ both have even degree in $G-e[Y']$. Therefore, $[X,Y]$ is an edge cut of $G$ such that $G[X]$ and $G[Y]$ are both even.
Therefore, by induction, we have shown that every graph $G$ has an edge cut $[X,Y]$ such that $G[X]$ and $G[Y]$ are even.