Grinberg-Introduction-Graph-Theory · Problem 3.7

Multigraphs

Mathematics — Graph Theory · multigraph-connectivity-submodularity

Problem

If GG is a multigraph, then conn⁡G\operatorname{conn} G shall denote the number of connected components of GG. (Note that this is 00 when GG has no vertices, and 11 if GG is connected.) Let (V,H,φ)(V, H, \varphi) be a multigraph. Let EE and FF be two subsets of HH. (a) Prove that conn⁡(V,E,φ∣E)+conn⁡(V,F,φ∣F)≤conn⁡(V,E∪F,φ∣E∪F)+conn⁡(V,E∩F,φ∣E∩F).(2)\begin{aligned} \operatorname{conn}(V, E, \varphi|_E) + \operatorname{conn}(V, F, \varphi|_F) \leq \operatorname{conn}(V, E \cup F, \varphi|_{E \cup F}) + \operatorname{conn}(V, E \cap F, \varphi|_{E \cap F}). \tag{2} \end{aligned} [Hint: Feel free to restrict yourself to the case of a simple graph; in this case, EE and FF are two subsets of P2(V)\mathcal{P}_2(V), and you have to show that conn⁡(V,E)+conn⁡(V,F)≤conn⁡(V,E∪F)+conn⁡(V,E∩F).\operatorname{conn}(V, E) + \operatorname{conn}(V, F) \leq \operatorname{conn}(V, E \cup F) + \operatorname{conn}(V, E \cap F). This isn't any easier than the general case, but saves you the hassle of carrying the map φ\varphi around.] (b) Give an example where the inequality (2) does not become an equality. [Solution: This is Exercise 3 on homework set \#3 from my Spring 2017 course; see the course page for solutions.]

Browse the problem library