Graph Theory Exam 1

from Graph Theory with Applications to Engineering & Computer Science by Nars

Path

An open walk in a graph that visits each vertex at most once.

Walk

A finite alternating sequence of vertices and edges, beginning and ending with vertices where each edge connects its two adjacent vertices, allowing for the possibility of revisiting vertices.

Circuit

A closed walk in a graph that visits each vertex at most once, except for the starting and ending vertex.

Connected

A graph is connected if there is a path between every pair of vertices, ensuring that all vertices are accessible from one another.

Component

A connected subgraph of a graph that is not connected to any additional vertices outside of it.

A simple graph with n vertices and k components can have at most

(n-k)(n-k+1)/2

Euler line

a closed walk that runs through every edge of the graph only once

Euler graph

a graph comprised of an Euler line

A unicursal graph/ an open Euler line

An open walk that covers every edge of a graph only once

union of two graphs

the graph formed by combining the vertex sets and edge sets of both graphs.

intersection of two graphs

the graph containing all vertices and edges that are common to both graphs.

ring sum of two graphs

another graph whose vertex set is the union of the vertex sets of each graph and whose edge set consists of edges that are in either graph but not in both

A graph is decomposed into two subgraphs

the union of the subgraphs is equivalent to the original graph and the intersection of the subgraphs is a null graph

Deletion

removal of either a vertex or edge from a graph

Fusion

two vertices are replaced by a single vertex which maintains all the edges connected to either of the original vertices or to both

An Euler graph is arbitrarily traceable from vertex v

every circuit in the graph contains v

Hamiltonian circuit

connected graph is a closed walk that traverses every vertex in the graph only once, excluding the starting vertex where the walk also ends

Hamiltonian path

Hamiltonian circuit that has had any one edge removed

Completeness

A simple graph which has an edge connecting every pair of vertices

tree

a connected graph without any circuit

A tree with n vertices

has n-1 edges

If there is only one path between every pair of vertices in a graph

graph is tree

Any connected graph with n vertices and n-1 edges

is a tree

a graph is a tree if and only if

it is minimally connected

a graph with n vertices, n-1 edges, and no circuits

is connected

a pendant vertex

a vertex of degree one

In any tree with two or more vertices, there are ___ pendant vertices

at least two

distance between two vertices

the length of the shortest path between them

eccentricity of a vertex

the distance between the vertex and the farthest away vertex in the graph

a center

a vertex with minimum eccentricity in a graph

every tree has ___ centers

one or two

radius of a tree

eccentricity of the center

diameter of a tree

length of the longest path in the tree

a rooted tree

a tree in which one vertex is distinguished from all the others

a binary tree

a tree with only one vertex of degree 2 with the rest of the vertices being of degree 1 or 3

connection between binary trees and rooted trees

every binary tree is a rooted tree

height of the tree

maximum level of any vertex in a binary tree

path length of a tree

the sum of the path lengths from the root to all pendant vertices

A spanning tree of a connected graph G

a tree that is a subgraph of G and contains all vertices of G

a branch

an edge in a spanning tree

a chord

an edge of G that is not in the spanning tree

A connected graph of n vertices and e edges has ___ tree branches and ___ chords

n-1 & e-n+1

Rank

difference between the vertices of a graph and the components

Nullity

the difference between the edges of a graph and its rank

Rank of a connected graph is ___ and the nullity is ___

n-1 & e-n+1

A fundamental circuit

a circuit formed by adding a chord to a spanning tree

a graph has ______ fundamental circuits as the number of chords

same number of

a cyclic interchange

the generation of one spanning tree from another by adding a chord to a spanning tree and then removing a branch from the fundamental circuit formed

The distance between two spanning trees

the number of edges present in one tree but not the other

the central tree

the spanning tree with the smallest maximal distance between the spanning tree and any other spanning tree

the weight of a spanning tree of a weighted graph

sum of the weights of all the branches in the spanning tree

A shortest spanning tree

A spanning tree with the smallest weight in a weighted graph

A degree-constrained shortest spanning tree

a spanning tree with an upper limit on the degree of every vertex imposed

A cut-set

a set of edges whose removal from a connected graph leaves that graph disconnected and for whom no proper subset disconnects that graph

connection between cut-sets and spanning trees

Every cut-set in a connected graph must contain at least one branch of every spanning tree of said graph.

fundamental cut-set

a cut-set containing exactly one branch of a spanning tree

ring sum of any two cut-sets in a graph

either a third cut-set or an edge-disjoint union of cut-sets