Re: Graph theory

In article <d9269f$qm9$1@xxxxxxxxxxxxxxxxxxxxxx>,
Brendan O'Sullivan <bos4@xxxxxxxxxxxx> wrote:
>I'm a secondary school teacher who does not have the good sense to leave
>maths alone during the holidays. I'm currently working through exercises but
>encounter difficulty, I bought Schaum's guide which helps but there are
>still things left unaswered.
>
>Could any kind soul help me with this one ?
>
>Show that if G is a simple graph with p vertives, where each vertex has
>degree >= (p-1)/2, then G must be connected. (It must be have something to
>do with how many vertices each component must have)

Exactly. Since the graph is "simple", there is at most one edge
between any two given vertices and no loops (edges starting and
finishing at the same vetex). Each connected component of G must have
at least [(p-1)/2] + 1 vertices: it has one vertex, and at least
(p-1)/2 other vertices which are the end points of the edges coming
out of that vertex. At least two components would give at least

2*([(p-1)/2] + 1) = p-1 + 2 = p+1 vertices

but the graph only has p vertices, so there cannot be more than 1
connected component. Thus, G is connected.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: Graph Theory: Cutting a Graph into Two in an Artificial Chemistry
    ... I start with a graph that has a single connected component (such that ... then I count that as a valid way that my original graph ... The set of all 'valid' splits from is the answer I want. ... It would probably be useful to know the size and complexity of the ...
    (sci.math)
  • Re: Topology with locally connected and expansion.
    ... the above theorem and that open subsets of a locally connected space are ... locally connected and that a connected component of a locally connected ... (Exercises left for you.) ... some collection P of connected clopen subsets that partition S. ...
    (sci.math)
  • Re: Topology with locally connected and expansion.
    ... Here's from the terse notes I took. ... the above theorem and that open subsets of a locally connected space are ... locally connected and that a connected component of a locally connected ... (Exercises left for you.) ...
    (sci.math)