Re: Simple Graph theory.. Please help!


Bob wrote:
> Let G be a graph of order n and let k be a positce integer with k<n.
>
> prove that if the min degree of gG >= (n+k-2)/2 Then G is k-connected.

Suppose you have a set X with size < k which disconnects G (i.e., G\X
breaks G into two graphs H and K). Try counting edges from X to X, X to
H and K, edges with both ends in H, and edges with both ends in K. You
should end up with fewer than the minimum degree condition guarantees.

--- Christopher Heckman

.

Relevant Pages

  • Re: finding minimum
    ... That is where the two functions ) intersect ... Graph the two functions, then show what curve is "m".. ... Prev by Date: ...
    (sci.math)
  • Re: zeros graph
    ... > the graph. ... I can only suggest providing the suggested test program others can look ... at and see if they can reproduce the problem. ... Prev by Date: ...
    (comp.soft-sys.matlab)
  • SumProduct or Countif
    ... and graph the results from Column C). ... I can't figure the syntax (or maybe I should modify a SubTotal ??) ... Prev by Date: ...
    (microsoft.public.excel)
  • Rolling data table??
    ... wanting the chart and graph to show just the last 12mos each time I update ... rather than just adjusting the series values? ... Prev by Date: ...
    (microsoft.public.excel.charting)
  • Re: plotted Average
    ... >i have a series of data as a line graph, i want my average to be plotted as ... > i have put the average 'series' in and told the chart to plot empty cells ... but the series is showing up as a whole number but ... Prev by Date: ...
    (microsoft.public.excel.charting)
Quantcast