Search results

  1. C

    Use Extreme Value Theorem

    Suppose f:[0,1]->R is continuous, f(0)>0, f(1)=0. Prove that there is a X0 in (0,1] such that f(Xo)=0 & f(X) >0 for 0<=X<Xo (there is a smallest point in the interval [0,1] which f attains 0) Since f is continuous, then there exist a sequence Xn converges to X0, and f(Xn) converges to f(Xo)...
  2. C

    Prove G contains a cycle of length at least k+1

    Tell me if I'm not on the right track. Use induction on k. Pick a path P of maximum length, and suppose vertex vi is a vertex on this path, which has degree at least k, with a set of adjacent vertices {w1,w2,…,wj}, the adjacent vertex set must be on the path. The minimum path length of a...
  3. C

    Prove G contains a cycle of length at least k+1

    This is a graph theory related question. Let G be a simple graph with min. degree k, where k>=2. Prove that G contains a cycle of length at least k+1. Am I suppose to use induction to prove G has a path length at least k first, then try to prove that G has a cycle of length at least k+1...
  4. C

    How to prove a simple graph is 2-connected?

    Problem: "Let G be a simple graph on n vertices such that deg(v)>= n/2 for every vertex v in G. Prove that deleting any vertex of G results in a connected graph." Well, I tried to find the min. case. Let k be the min. deg. of vertex in a simple graph, n is number of vertices in G so k =...
  5. C

    Graph Theory - bipartite related proof

    Okay, so by looking at my original assumption P(n-1)=[(n-1)^2/4]=[(n^2-2n+1)/4]=[n^2/4+(1-2n)/4] So now I need to prove that by adding additional one vertex in result of adding additional (2n-1)/4 edges for all n>5. So P(n)=P(n-1)+(2n-1)/4= [n^2/4+(1-2n)/4+(2n-1)/4]=[n^2/4] But how to...
  6. C

    Graph Theory - bipartite related proof

    How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4? Definition of bipartite graph: a graph whose vertex-set can be partitioned into two subsets such that every edge has one endpoint in one part and one endpoint in the other part. I try to...