Let $G = (V,E)$ be undirected graph, and let $(A, V/A)$ be a cut (A isn't empty), such that $|V/A|>|A| +1$
$\deg^A(v)$ Is the number of neighbors of v in A, and $\deg^{(V/A)}(v)$ Is the number of neighbors of v in V/A.
We also know that for every $v$ in $V/A$ - $\deg^{(V/A)}(v) \leq \deg^A(v)$.
Prove or disprove - at least $|E|/2$ edges are crossing the cut.
I am almost certain this claim is true, but after 2 days of trying proving it I gave up. Any Ideas on how to prove\disprove?
thanks.
The statement is false. Suppose there are $n>4$ elements of $V\setminus A$ each adjacent to all the others, and $3$ elements of $A$, each adjacent to the other two. Let there be an element $a\in A$ such that every element of $V\setminus A$ is adjacent to $a$, and let there be no other edges in $G$. Then there are are $\binom{n}{2}+3+n\geq3n+3$ edges in $G$, only $n$ of which cross the cut.