Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interpretation on the meaning of some graph theory statements

  1. Nov 11, 2012 #1
    Hello everyone,

    I'm studying basic graph theory, and my instructor gives me these statements to translate into pictures. I don't quite understand the meanings of the statements, but I have some thoughts about them.


    1/ "Any two vertices a, b are connected by at least 2 distinct paths of length 4"


    ==> Does this mean that any two vertices a, b are connected by at least 1 path of length 8?

    2/ "Any vertex of degree 2 is connected by a path of length 3 with a vertex of degree 3"

    ==> what does this mean ? (in terms of a picture)
    I'm thinking about a picture of 5 vertices A, B, C, D, E, where A --> B and A --> C but B --> D and C --> D and E --> D and E doesn't connect with A. Is this idea right ?

    3/ " Any 2 vertices connected by a path of length 3 have degree at most 2"

    ==> Is this statement saying something about the "diagonal" ? Because I'm thinking about a picture of 4 vertices A, B, C, D
    where A --> B and B --> C and C --> D. So A and D have degree at most 2 when I connect C with A and B with D.

    Would you please help me on these questions?
    Thank you in advance.:smile:
     
  2. jcsd
  3. Nov 11, 2012 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interpretation on the meaning of some graph theory statements
  1. Graph theory (Replies: 2)

Loading...