Graph Theory Help (3)

[Matt_F]

- Please prove that the following statements are equivalent for a graph G = (V,E) and V' ⊆ V:

a) V' is a vertex cover of G

b) V\V' is an independent set of G

c) V\V' is a clique in (G bar) - The G has a line over the top of it I think G bar is the correct term to describe this but I am not sure




Thank you

 

[SlipEternal]

Again, what have you tried so far? Where are you running into problems?

 

[Matt_F]

Again, what have you tried so far? Where are you running into problems?

I have mostly just been trying to think through this one a little bit. So for part a. if V' is a subset of V that means that V' is contained withing V. Therefore everything in V' is incident to something in V because it is contained in V making it a vertex cover.

part b and c I don't even understand what it is asking.

 

[SlipEternal]

Any time that you have equivalence, you need to consider how you want to prove it. You need to show that each conclusion follows from another. An independent vertex set is a set of vertices that are pairwise disconnected. So, assume you have \(\displaystyle V'\subset V\), and \(\displaystyle V'\) is a vertex covering of \(\displaystyle G\). That means that for all edges in \(\displaystyle G\) at least one of its endpoints is in \(\displaystyle V'\). So, consider \(\displaystyle V \setminus V'\). What would it mean if it was not an independent set? Why does the fact that \(\displaystyle V'\) is a vertex covering ensure that its complement is independent?

As for (c), \(\displaystyle \overline{G}\) is the edge complement of \(\displaystyle G\) in the complete graph on \(\displaystyle |V|\) vertices. So, if two vertices were adjacent in \(\displaystyle G\), they are not adjacent in \(\displaystyle \overline{G}\). If they were not adjacent in \(\displaystyle G\), they are adjacent in \(\displaystyle \overline{G}\).

So, you need to show (a) implies (b), (b) implies (c), and (c) implies (a).

 

[Matt_F]

Any time that you have equivalence, you need to consider how you want to prove it. You need to show that each conclusion follows from another. An independent vertex set is a set of vertices that are pairwise disconnected. So, assume you have \(\displaystyle V'\subset V\), and \(\displaystyle V'\) is a vertex covering of \(\displaystyle G\). That means that for all edges in \(\displaystyle G\) at least one of its endpoints is in \(\displaystyle V'\). So, consider \(\displaystyle V \setminus V'\). What would it mean if it was not an independent set? Why does the fact that \(\displaystyle V'\) is a vertex covering ensure that its complement is independent?

As for (c), \(\displaystyle \overline{G}\) is the edge complement of \(\displaystyle G\) in the complete graph on \(\displaystyle |V|\) vertices. So, if two vertices were adjacent in \(\displaystyle G\), they are not adjacent in \(\displaystyle \overline{G}\). If they were not adjacent in \(\displaystyle G\), they are adjacent in \(\displaystyle \overline{G}\).

So, you need to show (a) implies (b), (b) implies (c), and (c) implies (a).

Okay I need to get a better understanding on part a then. how do I know that V' is a vertex cover of G by being a subset of V?

 

[SlipEternal]

You assume it is a vertex cover. When three statements are equivalent, it means you assume (a) to prove (b), then forget (a) ever existed, and assume (b) to prove (c). Then, forget (b) existed, and assume (c) to prove (a).

Edit: In other words, if you have an arbitrary graph \(\displaystyle G\), and an arbitrary subset of the vertices \(\displaystyle V'\subseteq V\), if (a) is true, then so are (b) and (c). If (b) is true, then so are (a) and (c). If (c) is true, then so are (a) and (b). If (a) is not true, then neither is (b) nor (c). If (b) is not true, then neither is (a) nor (c). If (c) is not true, then neither is (a) nor (b).