Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the size of a maximum matching in a cycle of length $2k + 1$:

$$\large v_1, v_2,..v_{2k+1}$$

What is the size of a minimum vertex cover?

I know that If $G$ is a bipartite graph, then the maximum size of a matching in $G$ equals to the minimum size of a vertex cover in $G$. I am not sure on how to go on after this for a cycle of length $2k+1$

share|improve this question
5  
What have you tried? For instance, have you tried it for small graphs by hand $k = 1, 2, 3$ etc.? –  ShreevatsaR Jan 23 '13 at 16:45
    
An important aspect of the assignment is to work individually.. Bruce –  user59886 Jan 27 '13 at 23:28
    
@B.Shepherd: if you are the instructor of a course and you think the asker is one of your students cheating on their homework, you can consider the discussion about a similar incident before: One of my students may be getting math.SE to do their homework. Unfortunately, posting your comments here is likely to result in them simply being deleted. –  Rahul Jan 28 '13 at 0:10
    
@B.Shepherd: you may be interested in this meta thread: meta.math.stackexchange.com/questions/1277/… –  rschwieb Jan 28 '13 at 0:10
    
@B.Shepherd: I have converted this to a comment to prevent it from being deleted. –  robjohn Jan 28 '13 at 0:32

1 Answer 1

The size of a maximum matching is $k$.
On one hand, it's easy to find a matching with size $k$.
On the other hand, if you find a matching with size bigger than $k$, then the matching has vertexes not less than $2k+2$ as no vertex are in two edges of the matching. But the cycle has $2k+1$ vertexes only. The contradictory occurs.

The size of a minimum vertex cover is $k+1$.
On one hand, it's easy to find a vertex cover with size $k+1$.
On the other hand, if you find a vertex cover with size smaller than $k+1$, then it covers at most $2k$ edges as one vertex covers at most $2$ edges. But the cycle has $2k+1$ edges. The contradictory occurs.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.