Proving K-Extendability of a Bipartite Graph

  • MHB
  • Thread starter Aryth1
  • Start date
In summary, the conversation revolves around the problem of proving the extendability of a graph, where a graph is considered k-extendable if it has a certain number of vertices and if any k disjoint edges can be contained in a perfect matching. The question also involves a bipartite graph with a perfect matching and the condition that for any subset of the first partition, the number of adjacent vertices must be greater than or equal to the size of the subset plus k. The person asking for help is questioning the validity of the statement and is unsure of what they are missing.
  • #1
Aryth1
39
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
  • #2
Hi Aryth,

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

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

What's wrong? :/
 

FAQ: Proving K-Extendability of a Bipartite Graph

What is the "K-Extendability" of a bipartite graph?

The "K-Extendability" of a bipartite graph refers to the maximum number of new edges that can be added to the graph without creating a new odd cycle. It is used to measure the connectivity of the graph.

Why is proving K-Extendability important?

Proving K-Extendability is important because it helps us understand the structure and connectivity of a bipartite graph. It also has applications in various fields such as network routing algorithms, social network analysis, and data mining.

What is the process for proving K-Extendability of a bipartite graph?

The process for proving K-Extendability involves finding a matching of the graph and then using a mathematical proof to show that adding a certain number of new edges will not create a new odd cycle. This proof typically involves using induction and the properties of bipartite graphs.

Can a bipartite graph have a K-Extendability greater than its number of vertices?

No, a bipartite graph cannot have a K-Extendability greater than its number of vertices. This is because adding more than the maximum possible number of edges would create a new odd cycle, which contradicts the definition of K-Extendability.

Are there any efficient algorithms for finding the K-Extendability of a bipartite graph?

Yes, there are several efficient algorithms for finding the K-Extendability of a bipartite graph, such as the Edmonds' algorithm and the Hopcroft-Karp algorithm. These algorithms have a polynomial time complexity and are commonly used in computer science and network analysis.

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
1K
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
I Proof involving functional graphs and the injective property
Replies
3
Views
1K
MHB Prove the minimum and maximum edges in a graph
Replies
6
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