Hello,(adsbygoogle = window.adsbygoogle || []).push({});

My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and highlight the definitions with which I am having trouble.

SIMPLE GRAPH - is formally defined as an ordered pair (V,E) where V is a nonempty set of elements called vertices and E is a set of two-element subsets e = {u,v} of V called edges.

If some pairs of vertices have more than one edge joinging them, the result is called a MULTIGRAPH.

If there are loops ( which are edges beginning and ending at the same vertex) the result is called a PSEUDOGRAPH.

SUBGRAPH - of a graph is a set of vertices and edges, provided that all vertices incident with edges in the subgraph are included. In other words, a subgraph is a subset of the vertices and edges that itself forms a graph.

Types of Subgraphs

WALK - is a subraph that consists of a sequence of vertices and edges v_{0},e_{1},v_{1},e_{2},v_{2}...e_{n},v_{n}such that for 1 =< i =< n, the edge e_{i}joins vertices v_{i-1}and_{i}.

TRAIL - a walk in which no edges are repeated.

PATH - a trail in which no vertices are repeated except perhaps for the first and last vertex.

CIRCUIT - is a trail whose first and last vertices are the same.

CYCLE - is a path whose first and last vertices are the same.

Components of a Graph - Two vertices of a graph that are joined by a path are said to belong to the same component of the graph. If the whole graph is one component, then it is said to be connected.

I definition of a walk is making more sense to me now that I have written it out here. But I still am having trouble with components of a graph and when a graph is connected.

I also would like to know, if a graph is considered a multigraph, but it also has a loop, is it a multigraph or a pseudograph?

Any help is appreciated. Thankyou.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph Theory Definitions

**Physics Forums | Science Articles, Homework Help, Discussion**