Graph Theory Help (2)

[Matt_F]

-Let G be a graph. Denote the intersection number of G by in(G); denote that the clique cover number of G by θ(G). Please prove that the intersection number of G is equal to its clique number: in(G) = θ(G).


" Every vertex (set) contains at least one element in common with every other vertex contained within a Clique. I was thinking a long the lines of there is a set S* that contains the sets which make up the graph each set is a vertex and if one set intersects the other set then there is an edge between those vertices."


Thank you

 

[SlipEternal]

What do you think? What have you tried so far?

 

[Matt_F]

What do you think? What have you tried so far?

I said that the θ(G) is the minimum number of Cliques needed to cover the graph and in(G) is the | S min |. θ(G) has to be = in(G) because if the in(G) is the smallest number of different sets that still intersect. and θ(G) is the number Smallest number of cliques used to cover a graph and a clique contains all the vertices that share a common element.

 

[SlipEternal]

That is essentially it. I really don't know what else you are trying to show. Do you need a more detailed explanation? Consider what happens if one of those numbers is known, and figure out what you know about the graph to show that you can find the other to be equal.

 

[Matt_F]

That is essentially it. I really don't know what else you are trying to show. Do you need a more detailed explanation? Consider what happens if one of those numbers is known, and figure out what you know about the graph to show that you can find the other to be equal.

I think i need a more mathematically sound explanation or proof. I feel like I understand the concept it makes sense but I am having trouble actually proving it mathematically

 

[SlipEternal]

Then either assume one number is known and prove the other number must be the same or assume that both numbers are known to be different and show there is a contradiction.

 

[Matt_F]

Then either assume one number is known and prove the other number must be the same or assume that both numbers are known to be different and show there is a contradiction.

I will give that a try thank you very much for your help