Graph theory (matchings/connectivity)

In summary, the conversation is about solving three problems related to graphs and matching. The first problem states that if a graph G is (2k+1)-regular and remains connected after removing any set of edges with less than 2k edges, then G must have a perfect matching. The second problem involves showing that a graph with no isolated vertices and maximum degree d has a matching of size at least the number of vertices divided by (d+1). The last problem states that if a graph G is k-regular with an even number of vertices and satisfies certain conditions related to odd cycles, then G must have a perfect matching. The person has solved the first problem but is stuck on the last two.
  • #1
roadrunner
103
0
So my course is just getting further and further above my head. I got most of them but I'm stuck on these 3 and have no idea how to start them.

This is due friday so hopefully I can get input before that! :)




1) Let G be a (2k + 1)-regular graph, and assume that G - S is still connected
for any set S of edges with |S| < 2k. Prove that G has a perfect matching.


I know that there must be even number of vertices

I know that G-S means that every vertice is still guaranteed to have at least degree 2 (since it starts with degree 2k+1 and if all all of the edges is S were connected to a vertice then it will have 2k-1 less. )

But I don't know where to go from there or if that is even helpful?!


5) Let G be a simple graph with no isolated vertex. Assuming every vertex of G
has degree < d, show that a'(G) >= V (G)/(d + 1).

a' is the size of the maximum matching

12) Let G be a k-regular graph with an even number of vertices, and assume that
for any two odd cycles C1,C2 in G either V (C1) union V (C2) does not equal null ;, or there is an edge with one
end in V (C1) and the other in V (C2). Prove that G has a perfect matching. (Hint: suppose
for a contradiction that this is false, and choose a set X in V (G) of so that odd(G-X)>-|X|
is maximum and subject to this X is as large as possible, as in the proof of Tutte's theorem).
 
Physics news on Phys.org
  • #2
SO i figured out 1)

just stuck on last 2 :(
 

FAQ: Graph theory (matchings/connectivity)

1. What is graph theory?

Graph theory is a branch of mathematics that studies the properties and relationships of graphs, which are mathematical structures used to model pairwise relationships between objects. It has applications in various fields such as computer science, engineering, and social sciences.

2. What is a matching in graph theory?

A matching in graph theory refers to a set of edges in a graph where no two edges share a common endpoint. In other words, it is a selection of edges such that each vertex is incident to at most one edge in the set. Matchings are used to model relationships such as partnerships or assignments in real-world scenarios.

3. What is connectivity in graph theory?

Connectivity in graph theory refers to the ability to reach any vertex in a graph from any other vertex through a sequence of edges. A graph is said to be connected if there exists a path between every pair of vertices. Connectivity is an important concept in graph theory as it determines the robustness and efficiency of a network.

4. How is graph theory used in computer science?

Graph theory has many applications in computer science, such as in the design and analysis of algorithms for problems like shortest path finding, network flow, and scheduling. It is also used in the modeling and optimization of computer networks, transportation systems, and social networks.

5. What are some real-world examples of graph theory?

Graph theory has numerous real-world applications, including in the study of social networks, transportation systems, and computer networks. For example, social media platforms use graph theory to suggest friends, while GPS navigation systems use it to find the shortest route between two locations. Graph theory is also used in designing efficient airline routes and optimizing telecommunication networks.

Similar threads

Back
Top