Where $ x$ and $ y$ are non-adjacent pairs in a simple connected graph prove that $ deg(x) + deg(y) \geq n-1$
Am i reading something wrong? This was a workshop question given to me in preparation for exams but I don’t see how this is true.
A simple connected graph is a graph such that given any two points on the graph $ a$ , $ b$ we can find a path from $ a$ to $ b$ , without multiple edges and no loops. Take a graph $ n=4$ for example:
If i let $ b$ and $ d$ be my $ x$ and $ y$ then the equation holds as $ deb(b) + deg(d) = 1 + 2 = 3 \geq 4-1 = 3$
However, if we remove the edge between $ a$ and $ d$ then is the graph not still a simple connected graph where $ d$ and $ b$ are non-adjacent? Because in this case $ deg(b) + deg(d) = 2$ which is less than $ 3$ . Therefore the equation doesn’t seem to hold. I’m not quite sure what I’m missing here.