MHB Proving K-Extendability of a Bipartite Graph

  • Thread starter Thread starter Aryth1
  • Start date Start date
AI Thread 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? :/
 

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

Hot Threads

Recent Insights

Back
Top