Graph Theory definitions

Question 1

Define the degree of a vertex

Answer 1

This refers to the number of edges which are attached to a vertex, with a loop counting as two.

Question 2

Define Isomorphic Graphs

Answer 2

These are “equivalent,” graphs, meaning they have the same number of edges, with all edges connecting the same vertices.

Question 3

Define a connected graph

Answer 3

A connected graph is one where every vertex is connected to all other vertices, either directly or indirectly.

Question 4

Define a planar graph

Answer 4

A kind of graph where no edges cross over each other

Question 5

Define the face of a Planar graph

Answer 5

The face of a planar graph refers to the region bounded by edges in the graph, including the outer region.

Question 6

Define a complete graph

Answer 6

A complete graph is where every vertex is connected to every other vertex by an edge

Question 7

Define a simple graph

Answer 7

A graph where there is no loops or multiple edges

Question 8

Define a bridge

Answer 8

A bridge is a single edge in a connected graph that would cause the graph to be disconnected if that edge were removed.

Question 9

When can Euler’s formula be applied.

Answer 9

:If the graph is connected
:If the graph is a planar graph

Question 10

Define a walk.

Answer 10

A walk will commence at one vertex and follow any path to end at another vertex.

Question 11

Define a trail.

Answer 11

A trail is a walk with no repeated edges, although a vertex can be repeated.

Question 12

Define a path

Answer 12

A path is a walk with no repeated edges or vertices.

Question 13

Define a circuit

Answer 13

A circuit is a trail that begins and finishes at the same vertex.

Question 14

Define a cycle

Answer 14

This is a path the begins and finishes at the same vertex.

Question 15

Define a Euler trail

Answer 15

A trail which contains exactly two vertices that have an odd degree, with the walk starting from one of the odd degree vertices and finishing at the other.

Question 16

Define a Euler circuit

Answer 16

A Euler circuit is a walk that finishes and ends at the same vertex, where every vertex has an even degree.

Question 17

Define a Hamiltonian path

Answer 17

This is a path which visits every vertex once.

Question 18

Define a Hamiltonian cycle

Answer 18

This is a cycle that reaches every vertex.

Question 19

Define a tree

Answer 19

This is a connected graph where there are no multiple edges, loops, or cycles.
A tree will always have n-1 edges.

Question 20

Define a spanning tree

Answer 20

A tree which connects all vertices of a graph.