Graph Theory Exam 1

Graph

A pair of (V,E) where V is the vertex set and E is the edge set

Vertex Set

A non-empty set that contains all the vertices/ noodes

Edge Set

A set of unordered pair of vertices that represent the edges

Null Graph

A graph that has no edges and have atleast one vertex

Trivial Graph

A graph that contains a single element

Loop

If an edge connectes to its self or a more mathematical way to describe is when e is an element of the edge set and e = uu where u is a vertex

Parallel Edges

If two edges e1 and e2 connects the same 2 vertices

Simple Graph

A graph with no loops or parallel edges

Multigraphs

A graph with self-loops and parallel eges

Finite Graph

A graph whose order is not infinite

Order

Magnitude or Number of vertices

Size

Magnitude or number of edges

Neighbors

Vertices that are adjacent to each other or mathematical there exist a if u,v is an element of the vertex set and there exist a edge uv such that it connects vertices u,v

Neighborhood

Collection of Neighbors

Clique

A set of pairwise adjacent vertices

Independent Set

A set of nonadjacent vertices

n-vertex graph

A graph that contains n vertices

(n,m) graph

a graph that contains n vertices and m edges

n-Complete Graph

Denoted by Kn it is a graph whose order is n and where, for all vertices u,v there exist an edge uv that connects them

Maximum number of edges (Theorem)

The number of edge in a graph is at most nC2

Number of labelled graph in a graph

There is an 2^(nC2) number of labelled graph in a graph with order n

Bipartite graph

If there exist set of vertices x,y which is a subset of the vertex set V such that x and y are pairwise disjoint and if there’s an edge e = uv such that u is an element of x and v is an element of y

Complete Bipartite

A bipartite graph is complete if for all v element of x which is a subset of the vertex set V is adjacent to u which is an element of the vertex subset y (Notation K(m,n) )

Star

A graph whose written as K(1, n -1)

Size of a complete bipartite graph

The size of a complete bipartite graph K(m,n) is m*n

Directed Graph (Digraph)

a graph G = (V, E) where V = ∅ and E ⊆ V ×V . The edges referred to as arcs or directed edges are determined by an ordered pair (u, v) of vertices. The edges in an undirected graph are unordered pair {u, v}} of vertices. For an arc (u, v), we call u as its tail and v as its head so if e = uv then u = tail(e) and v = head(e). Arcs are drawn using directed arrows from its tail to its head.

Weighted Graph

A weighted graph is an ordered pair (G, d), where G is a graph, and d is a weight function defined as d : E → R that associates each edge e of G a real number d(e). By the weights in a weighted graph, we mean the weights on the edges. However, sometimes weights can be assigned to vertices also.

Subgraph

H of a graph G is a graph such that V (H) ⊆ V (G) and E(H) ⊆ E(G)

Spanning Subgraph

If H is a subgraph of G such that V (H) = V (G)

Induced Subgraph

A subgraph H of G is said to be an induced subgraph of G if E(H) = { uv ∈ E(G) | u, v ∈ V (H) }.

Complement of a graph

The complement of a graph G, denoted by G, is the graph whose vertex set is V (G) = V (G) and the edge set E(G) = { uv | u, v ∈ G, uv /∈ E(G) }. This implies that e ∈ E(G) iff e 6inE(G)

Path

a path is a sequence of vertices connected by edges, where no vertex is repeated.

Trail

a trail is a sequence of vertices connected by edges where no edge is repeated, but vertices can be repeated.

Regular Graph

is a graph where each vertex has the same degree (number of edges connected to it). If every vertex has degree kkk, the graph is called a k-regular graph.

Walk

a walk is a sequence of vertices and edges where vertices and edges can be repeated, and each edge connects consecutive vertices in the sequence.

Connected Graph

a connected graph is a graph in which there is a path between every pair of vertices, meaning no vertex is isolated.

Tree

a tree is an acyclic connected graph, meaning it is a graph with no cycles and there is exactly one path between any pair of vertices

Adjacency Matrix

In graph theory, an adjacency matrix is a square matrix used to represent a graph, where the rows and columns correspond to the graph's vertices, and each entry A[i][j] indicates whether an edge exists between vertex i and vertex j:

• A[i][j]=1 if there is an edge.

• A[i][j]=0 if there is no edge.

For weighted graphs, the entries contain the weights of the edges instead of 1 or 0.

Incidence Matrix

In graph theory, an incidence matrix is a matrix that represents the relationship between vertices and edges of a graph.

• If a graph has nnn vertices and mmm edges, the incidence matrix is an n×m.

• Each entry I[i][j]is:

  • 1 if vertex iii is incident to edge j (connected by it).

  • 0 otherwise.

For directed graphs, the entries can be 1 for the starting vertex and −1 for the ending vertex of an edge.

Laplacian

In graph theory, the Laplacian matrix (or graph Laplacian) is a matrix representation of a graph that highlights its structure and connectivity. For a graph with n vertices, the Laplacian matrix L is defined as:

L=D−A

Where:

• Dis the degree matrix (a diagonal matrix where each entry D[i][i]is the degree of vertex i).

• AAA is the adjacency matrix of the graph.

Properties:

• L[i][i]diagonal entries) = degree of vertex i.

• L[i][j]off-diagonal entries) = −1 if there is an edge between vertex i and vertex j, otherwise 0.

• The sum of each row in Lis 0.

The graph Laplacian is widely used in areas like spectral graph theory, network analysis, and machine learning.