Proving K-Extendability of a Bipartite Graph

  • Context: MHB 
  • Thread starter Thread starter Aryth1
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on proving the k-extendability of a bipartite graph, specifically a graph G[A,B] with a perfect matching. A graph is defined as k-extendable if it contains at least 2k + 2 vertices and any k disjoint edges can be included in a perfect matching. The key condition discussed is that for any subset S of A, the neighborhood N(S) must satisfy |N(S)| ≥ |S| + k. A participant raises a concern regarding the implications of this condition, suggesting that it leads to a trivial case when k is less than or equal to zero.

PREREQUISITES
  • Understanding of bipartite graphs and perfect matchings
  • Familiarity with graph theory concepts such as k-extendability
  • Knowledge of neighborhood functions in graph theory
  • Basic mathematical proof techniques
NEXT STEPS
  • Study the concept of k-extendability in greater depth
  • Research perfect matching conditions in bipartite graphs
  • Explore the implications of neighborhood size in graph theory
  • Learn about advanced proof techniques in combinatorial optimization
USEFUL FOR

Mathematicians, computer scientists, and students specializing in graph theory or combinatorial optimization who are interested in advanced topics related to bipartite graphs and matching theory.

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