Department of Mathematics Elementary Graph Theory Lecture 6
Basic Properties
Walk
A walk is an alternating sequence of vertices and edges of a graph.
Vertex can be repeated
Edges can be repeated
Open walk
A walk is said to be an open walk if the starting and ending vertices are
different.
Closed walk
A walk is said to be closed walk if the starting and ending vertices are
identical.
Trial
A walk with no repeated edges is called trial.
Circuit
A circuit is a closed walk that does not contain any repeated edges.
Path
Is a trial in which neither vertices nor edges are repeated.
Cycle
Is a circuit in which the vertices does not repeated.
A graph
v2v1v3v1v4v1v5v7 is a v2 v7 walk and it is open , v2v1v3v1v5v7 v5v2 is a closed walk
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 6
v2 v1v3v4v1v5v7 is a v2 v7 trial
v2v3v1v5v6v7 v5v4v1v2 is a closed trial (is a circuit)
v2 v3v1v4 v5v6v7 is a v2 v7 path , v2v5v7 also is a v2 v7 path
v2v1v5v4v3v2 is a closed path ( is a cycle)
Geodesic
A shortest v2 v7 path is called geodesic
Connected graph
A graph G is said to be connected graph, if every pair of vertices of a graph G
is joined by a path. Otherwise G is disconnected.
Connected graph Disconnected graph
Component
A maximal connected subgraph of G is called component, thus disconnected
graph has at least two components.
Length
The length of a walk, trial, path or cycle is its number of edges.
Distance
The distance between two vertices u and v in a graph G is the minimum
lengths of all u-v path in G, and it is denoted by dG (u , v) . If no u-v path
exists, then dG (u , v) .
Girth
The girth of a graph G is the length of a shortest cycle and is denoted by
gir (G ) .
Circumference
The circumference of a graph G is the length of a longest cycle and is denoted
by c (G )
Dr. Didar A. Ali 2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller bilal-guma. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.45. You're not tied to anything after your purchase.
