MHB Undirected graph proof, Set intersection

[c4nn3t]

Hello all, I'm a bit stumped when it comes to formal proofs. I

PART A: "Let A,B ⊆{1,2...n} be two sets with A,B > n/2. Prove that the intersection of A ∩ B is nonempty."
This part I used contradiction, but didn't get everything. I assumed that if the intersection of A and B was empty, then A∪B is A+B, which is n>2 + n>2 = n. A∪B⊆{1,2,...n}, so therefore A∪B must be <= |{1,2...n}| = n. Then, n >= |A∪B| > n, which results in a contradiction.
Is this enough of a formal proof, or is there a step I missed?PART B: "Let Z=(J,K) be an undirected graph on x vertices. Each vertex has degree >x/2. Prove that Z is connected."
I wasn't sure how to start off proving this one. Supposedly solving part A helps solve this. Any two nodes are adjacent to more than >x/2 of the nodes, but I'm not sure how to turn this into a formal proof.

I'd really appreciate some input to get going, thanks so much in advance!

 

[Sudharaka]

Hello all, I'm a bit stumped when it comes to formal proofs. I

PART A: "Let A,B ⊆{1,2...n} be two sets with A,B > n/2. Prove that the intersection of A ∩ B is nonempty."
This part I used contradiction, but didn't get everything. I assumed that if the intersection of A and B was empty, then A∪B is A+B, which is n>2 + n>2 = n. A∪B⊆{1,2,...n}, so therefore A∪B must be <= |{1,2...n}| = n. Then, n >= |A∪B| > n, which results in a contradiction.
Is this enough of a formal proof, or is there a step I missed?PART B: "Let Z=(J,K) be an undirected graph on x vertices. Each vertex has degree >x/2. Prove that Z is connected."
I wasn't sure how to start off proving this one. Supposedly solving part A helps solve this. Any two nodes are adjacent to more than >x/2 of the nodes, but I'm not sure how to turn this into a formal proof.

I'd really appreciate some input to get going, thanks so much in advance!

Hi c4nn3t, :)

The idea behind your first proof is correct. What you have used is the fact that for any two finite sets $A,\,B\subseteq \{1,\,2,\,\cdots,\,n\}$,

\[|A\cup B|=|A|+|B|-|A\cap B|\]

Supposing $|A\cap B|=0$ we have,

\[|A\cup B|=|A|+|B|>n\]

Also since, $A\cup B\subseteq \{1,\,2,\,\cdots,\,n\}\Rightarrow |A\cup B|\leq n$

Both of these conditions cannot be true.

 

[Evgeny.Makarov]

PART B: "Let Z=(J,K) be an undirected graph on x vertices. Each vertex has degree >x/2. Prove that Z is connected."

Hint: Prove that not only the graph is connected, but its diameter is $\le 2$. Here the diameter is the greatest distance between any pair of vertices, and the distance between two vertices is the length of a shortest path between them. In other words, diameter 2 means that one can go from one vertex to any other vertex in at most two steps.

 

[c4nn3t]

AH, okay, now that first part makes sense, thanks so much for that!

I'm not still sure if I've grasped the second part. Also, I forgot to mention, J is the number of vertices, and E is the number of edges in the graph, I'll update the original post to reflect that. So I'd start out saying for a graph Z, each vertex J has degree greater than x/2. This must mean that K is also > x/2. I want to show that K is <= 2 between any two vertices, which I think is the step I'm having difficulty finding.
So once I prove that the graph is diameter <=2, how does that lead to it being connected? Ultimately, I state that the G is connected if J has connectivity n-1. Do I need to consider if the graph is Eulerian?

Still quite confused with this one, maybe I'm not picking at my brain hard enough... (Fubar)

 

[Evgeny.Makarov]

Also, I forgot to mention, J is the number of vertices, and E is the number of edges in the graph

But post #1 says that $J$ is the set of vertices, and $K$ (and not $E$) is the set of edges. Meanwhile, the number if vertices is $x$, i.e., $|J|=x$.

You shouldn't confuse sets and their cardinalities, i.e, the number of elements. These are entities of different type. The cardinality of $A$ is often denoted by $|A|$. For example, the phrase "A∪B is A+B, which is n" in post #1 should in fact say, "$|A\cup B|$ is $|A|+|B|$, which is $n$".

So I'd start out saying for a graph Z, each vertex J has degree greater than x/2. This must mean that K is also > x/2. I want to show that K is <= 2 between any two vertices

You cannot say, "$K$ between two vertices" because $K$ is the set of all edges. Picking two concrete vertices does not change $K$; it is defined once for all in the scope of this problem.

So once I prove that the graph is diameter <=2, how does that lead to it being connected?

Hmm, if I can walk from any vertex to any other vertex in at most two steps, why does it follow that I can walk from any vertex to any other vertex in any number of steps?

Ultimately, I state that the G is connected if J has connectivity n-1. Do I need to consider if the graph is Eulerian?

No.

Pick two vertices $u$ and $v$. Let $U$ be the set of vertices adjacent to $u$, and let $V$ be the set of vertices adjacent to $v$. Then by assumption $|U|>x/2$ and $|V|>x/2$ where $x=|J|$. Obviously, $U\subseteq J$ and $V\subseteq J$. Do you think you can apply Part A from post #1 to this situation?