Discrete graph terms

Graph Theory terms

Graph

A graph is a non-empty set of vertices & edges connecting vertices.

Parallel

Edges that have same end vertices are parallel.

Simple Graph

A graph without any parallel edges or loop.

Empty Graph

A graph with no edges.

Null Graph

A graph with no vertices.

Trival Graph

A graph with only one vertex.

Adjacent

Edges are adjacent if they share a common end vertex.

Pendant Vertex

A vertex with degree 1.

Pendant Edge

An edge that has a pendant vertex as an endpoint.

Isolated Vertex

Vertex with degree 0.

Complete Graph

A simple graph with n vertices in which every vertex is connected to all other vertices.

Cycle Graph

n >= 3

Wheel Graph

Adds an additional vertex in the middle to a cycle.

Biparte Graph

A simple graph G(V,E), every edge in G is only connecting a vertex from V1 to V2 & vice versa.

Walk

An infinite sequence of vertices and edges

Closed Walk

A walk where initial and terminal vertex is the same

Trail

A walk with no repeated edges

Path

A walk with no repeated edges and vertices expect for initial and terminal

Cycle

A closed path

Circuit

A closed trail

Cut Vertex

A vertex of connected graph whose removal increases the number of connected components

Cut Edge

An edge whose removal increases the number of connected components

Tree

A connected undirected graph with no circut/cycle

Forest

A graph if it is circuit-free and not connected

Rooted Tree

A tree in which one vertex has been designed as the root & every edge is away from the root

Internal Vertices

Vertices that have children

Leaf

Vertex that don’t have children

Euler Walk

A walk that uses every edge exactly once

Euler Circuit

A closed walk that uses each edge exactly once

Theorem for Euler Walk

Has a Euler walk if exactly two veracities have an odd degree

Theorem for Euler Circuit

Has Euler circuit if every vertex has an even degree

Km,n Graph for Euler Walk

either m or n = 2 and other is odd degree

Km,n Graph for Euler Circuit

m & n = even

Hamiltonian Path

A path uses every vertex exactly once

Hamiltonian Circuit

A circuit that uses every vertex exactly once