MHB Proving K-Extendability of a Bipartite Graph

  • Thread starter Thread starter Aryth1
  • Start date Start date
Click For Summary
The discussion centers on proving the k-extendability of a bipartite graph, specifically under the condition that for any subset S of set A, the neighborhood N(S) satisfies |N(S)| ≥ |S| + k. The original poster struggles to find relevant results on extendability and seeks assistance after unsuccessful attempts at proving the statement. A participant questions the logic, noting that if there is a perfect matching, it implies |A| = |B| and that the condition leads to a trivial conclusion where k must be less than or equal to zero. The conversation highlights the complexities in understanding the implications of perfect matchings in bipartite graphs and the conditions for k-extendability.
Aryth1
Messages
38
Reaction score
0
I was asked to see if I could prove this was true, but I have been totally unable to. I can't find many results about extendability and so I have had a lot of trouble. After days of thinking about it without anything to show, I figured that I'd ask for some help here. Here's the problem:

A graph is k-extendable if $|V(G)|\geq 2k + 2$ and for any k disjoint edges, there is a perfect matching containing them. Let $G[A,B]$ be a bipartite graph with a perfect matching. If for any $S\subset A$, $|N(S)|\geq |S| + k$, show that $G$ is k-extendable.

Any help is greatly appreciated!
 
Physics news on Phys.org
Hi Aryth,

I think I'm missing something, if there is a perfect matching in a bipartite graph then $$|A|=|B|$$ and $$N(A)=B$$.

And from $$|N(S)| \geq |S| + k$$ with $$S=A$$ we get $$k\leq 0$$ so the statement is trivial.

What's wrong? :/
 

Thread 'Please Explain (actually explain) The Monty Hall Problem'

Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
View full post »

Similar threads

MHB Bipartite Graphs: Does $\alpha(G) =|U|$?
Replies
1
Views
2K
MHB A Subset of a Graph with No Perfect Matching
Replies
1
Views
2K
MHB Understanding Two Graph Theory Problems
Replies
2
Views
2K
MHB Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$
Replies
1
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
Replies
1
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
Replies
1
Views
2K
MHB Probability of Having a Totally Dominating Set (Probabilistic Methods)
Replies
1
Views
2K
MHB Prove the minimum and maximum edges in a graph
Replies
6
Views
2K
I Proof involving functional graphs and the injective property
Replies
3
Views
1K
MHB Show Inequality: Explain Why $g(k) \geq \frac{3^k}{2k+1}$ in Football Matches
Replies
7
Views
2K