Interpretation on the meaning of some graph theory statements

Click For Summary
SUMMARY

This discussion focuses on interpreting specific statements in basic graph theory. The statements include the connectivity of vertices by distinct paths, the relationship between vertices of different degrees, and the implications of path lengths on vertex degrees. The participants seek clarification on how to visualize these concepts through diagrams, particularly regarding paths of lengths 3 and 4 and their associated vertex degrees.

PREREQUISITES
  • Basic understanding of graph theory concepts, including vertices and edges.
  • Familiarity with vertex degree and path length in graphs.
  • Ability to visualize graph structures and relationships.
  • Knowledge of graph representation techniques, such as adjacency lists or matrices.
NEXT STEPS
  • Study the concept of "distinct paths" in graph theory.
  • Learn about vertex degrees and their implications in graph connectivity.
  • Explore visual representation techniques for graph theory statements.
  • Investigate the properties of paths in graphs, particularly focusing on path lengths and their effects on vertex degrees.
USEFUL FOR

Students of graph theory, educators teaching graph concepts, and anyone interested in visualizing and interpreting graph structures and relationships.

Ceci020
Messages
10
Reaction score
0
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:
 
Physics news on Phys.org

Similar threads

Undergrad A way to comprehend the geometry of a hypercube
  • · Replies 2 ·
Replies
2
Views
2K
High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Chiral symmetries in E[SUP]^n[/SUP]
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Miller indices and periodic boundary conditions
  • · Replies 0 ·
Replies
0
Views
3K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Circuits or edge-disjoint unions of circuits in a connected graph
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Difficult to understand the solution provided in the video (travelling salesman problem)
  • · Replies 3 ·
Replies
3
Views
3K