2
$\begingroup$

Can anybody help me prove this inequality, please? I am not used to proving mathematical statements, so tips and hints are appreciated.

Show that every simple graph $G(V, E)$ satisfies the following inequality $$m\geq n-k$$ where $n = |V|$, $m = |E|$ and $k = \omega(G)$ (that is the number of connected components).

$\endgroup$
4
  • $\begingroup$ Welcome to stackexchange. Please edit the question to tell us what $\omega$ is, and what you have tried and where you are stuck. $\endgroup$ Commented Jul 4, 2019 at 16:58
  • $\begingroup$ The concept of connectedness is still a bit blurry for me, but I have checked cases where that inequality holds. I don't even know how to start, so hints are welcome. $\endgroup$ Commented Jul 4, 2019 at 17:03
  • $\begingroup$ Do you know what a spanning tree is? $\endgroup$
    – saulspatz
    Commented Jul 4, 2019 at 17:05
  • $\begingroup$ No, we haven't been taught what spanning tree is. $\endgroup$ Commented Jul 4, 2019 at 17:06

2 Answers 2

1
$\begingroup$

Each component is connected so suppose it has $n_i$ vertices, then it should have at least $n_i-1$ edges (think about a minimal connected acyclic simple graph: it is a tree). Thus the number of edges added over all the components is at least $\sum_{i=1}^k(n_i-1)$. So

$$m \geq \sum_{i=1}^k(n_i-1) =\sum_{i=1}^kn_i -k=n-k,$$ where $n$ is the total number of vertices in the graph.

$\endgroup$
1
$\begingroup$

Start with a graph with just $n$ vertices and no edges. Then $k = n$ since every vertex is its own connected component. Then $$ m = 0 = n - k . $$ Now add the edges one at a time. Each new edge increases the left side by $1$ and may or may not increase $k$, depending on whether it joins two previous components or not. So that new edge may or may not increase the right side.

$\endgroup$
4
  • $\begingroup$ This argument can be used to build some induction type of argument. $\endgroup$
    – user459879
    Commented Jul 4, 2019 at 17:18
  • 1
    $\begingroup$ @WesleyStrik Of course. It's just induction presented with words that (I think) make the idea clearer than would a more formal proof. Whether more formality is required depends on what the OP's teacher wants. As a teacher I would prefer the less forrmal argument with words. $\endgroup$ Commented Jul 4, 2019 at 17:24
  • $\begingroup$ I think this would be the main step, I just wanted to add for any future readers. If they want to elaborate on your argument, use it as part of the inductive step in an induction argument, right? This would make the step from $m$ edges to $m+1$ edges, where you induct on the number of edges for instance. Either way, you use this kind of argument. Unfortunately my teacher prefers a formal argument to wrap the logic :P In this case, I prefer having you as a teacher. $\endgroup$
    – user459879
    Commented Jul 4, 2019 at 17:29
  • $\begingroup$ Induction adds nothing extra to this argument. It just gives a name to the idea you are describing of slowly adding the edges starting from a graph on $n$ vertices but without any edges. $\endgroup$
    – user459879
    Commented Jul 4, 2019 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .