Question about the proof of every graph $G$, $G$ contains a bipartite subgraph $H$ such that $|E(H)| > 1/2|E(G)|$

956 Views Asked by At

Part of this proof involves choosing $v \in V(G)$ for $n(G) > 2$ that is not incident to all of $E(G)$. This is because at most two vertices can be incident to all of $E(G)$. Why is that last statement true? I'm sure it's trivial, but I can't wrap my head around it.

1

There are 1 best solutions below

2
On BEST ANSWER

Reason: Every edge has only two end points.