2

Show that any connected, undirected graph $G = (V,E)$ satisfied $|E|≥|V|-1$. Can I use math induction by $n = |V|$ here (remove and add vertex)?

lulu
  • 70,402
Simankov
  • 131
  • In principle, yes. Can you show that you can remove a vertex without disconnecting the graph? – lulu Aug 10 '15 at 21:51
  • It's probably easier to use induction on the number of edges, and look at what happens when you delete an edge. – James Aug 10 '15 at 21:57
  • @lulu I mean mentally removing vertex with adjoint edges (There is one edge or more because of "connected" graph). – Simankov Aug 10 '15 at 22:05
  • Sure, but if you delete a random vertex the graph may break into pieces. It is true that there are always vertices you can safely delete, but it merits an argument. – lulu Aug 10 '15 at 22:07
  • Suppose you say "Any simply connected graph is blah." The word "any" means "no matter which one" so in effect it means "every". Now suppose you say "There isn't any connected graph that is blah." Then "any" means something closer to "some"; it denies that there is some connected graph that is blah. Now suppose you say "Show that any connected graph is blah." That could mean "Pick any connected graph and show that it is blah." But that is not the intended meaning. I would use the word "every" on this occasion. ${}\qquad{}$ – Michael Hardy Aug 10 '15 at 22:10
  • @lulu, Thank, I got it. Time to think:) – Simankov Aug 10 '15 at 22:13
  • @MichaelHardy Okay, this was phrase from Cormen: Introduction to Algorithms. But I'll think about it. – Simankov Aug 10 '15 at 22:14

2 Answers2

1

Yes. The point is that you can build up the graph one vertex at a time, maintaining connectivity: if $u$ is a vertex you already have and $v$ is a vertex you don't, consider a path from $u$ to $v$ and add the first vertex on that path that you don't already have (together with the edges joining it to the vertices you already have).

Robert Israel
  • 448,999
1

Here's an argument (still induction on $|V|$) that proceeds by removing vertices:

The claim is clearly true if $|V|$ is $1$ or $2$. To proceed by induction we need to know that we can delete a vertex without disconnecting the graph. To see that this is always possible: Pick a node $\nu$ at random. Now for any node $n$ define its distance from $\nu$, $l(n)$, to be the length of a minimal path between $\nu$ and $n$. I claim that you can always delete any node $\hat n$ with maximal $l(\hat n)$: Take any two nodes other than the one you want to delete. Both have a path to $\nu$ that does not pass through $\hat n$ (otherwise they would be further from $\nu$ then $\hat n$ is). Since the two nodes can still reach $\nu$ once $\hat n$ is gone, they can reach each other.

Now the induction is easy: deleting $\hat n$ leaves a graph to which we can apply the induction hypothesis. When you restore $\hat n$ (along with all of the edges it was a part of) you increase $|V|$ by exactly $1$ and you increase $|E|$ by at least $1$.

lulu
  • 70,402