Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

Graph theory is the study of graphs, which is defined as an ordered pair $G = (V, E)$ comprising a set $V$ of vertices or nodes or points together with a set $E$ of edges or arcs or lines, which are 2-element subsets of $V$ (i.e. an edge is associated with two vertices, and that association takes the form of the unordered pair comprising those two vertices).

Questions involve graph properties, graph algorithms, proofs and examples involving graphs, and applications of graph theory to other fields or practical ends.

Use instead for questions about graphing or plotting of functions.

23857 questions
77
votes
4 answers

Graph theory: adjacency vs incident

Okay, so I think if 2 vertices are adjacent to each other, they are incident to each other....or do I have it wrong? Is this just different terminology. I thought I was totally clear on this for my class, but now I am doubting myself reading the…
pqsk
  • 875
54
votes
7 answers

What is difference between cycle, path and circuit in Graph Theory

I am currently studying Graph Theory and want to know the difference in between Path , Cycle and Circuit. I know the difference between Path and the cycle but What is the Circuit actually mean.
Sudeep Acharya
  • 701
42
votes
4 answers

Difference between a sub graph and induced sub graph.

I have the following paragraph in my notes: If $G=(V,E)$ is a general graph . Let $U\subseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ , then $H=(U,F)$ is also a general graph and $H$ is a subgraph…
patang
  • 797
38
votes
6 answers

How to calculate the number of possible connected simple graphs with $n$ labelled vertices

Suppose that we had a set of vertices labelled $1,2,\ldots,n$. There will several ways to connect vertices using edges. Assume that the graph is simple and connected. In what efficient (or if there is no efficient way, you can just tell me whatever…
Shoeinger Veronica
  • 413
36
votes
9 answers

Given a simple graph and its complement, prove that either of them is always connected.

I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph. Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with…
ivt
  • 1,587
33
votes
10 answers

Proving that the number of vertices of odd degree in any graph G is even

I'm having a bit of a trouble with the below question Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$. Prove that the number of vertices of odd degree in…
sandman001
  • 435
26
votes
1 answer

Human checkable proof of the Four Color Theorem?

Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his beautiful blogs posed the following open problem: Are…
Mohammad Al-Turkistany
  • 952
26
votes
3 answers

Difference between graph homomorphism and graph isomorphism

I am still not getting how graph isomorphism and homomorphism differ. Can anyone show me two graphs that are homomorphic, but not isomorphic? Also, Wikipedia says that when the function and the inverse function are both homomorphic, two graphs are…
Absolutio Zaka
  • 453
24
votes
3 answers

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$. How would I show this? I understand that a cycle is a sequence of non-repeated vertices and the degree of a graph is the number of neighbors the vertex…
user126032
  • 527
24
votes
8 answers

Why does a full binary tree of $n$ leaves have $2n-1$ nodes?

A complete binary tree is defined as a tree where each node has either $2$ or $0$ children. A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the number of leaves. I haven't however been able to find…
user26649
24
votes
1 answer

What is the difference between a loop, cycle and strongly connected components in Graph Theory?

Which graph is/contains a cycle? loop? strongly connected component? I believe the following is correct in regards to graphs above: all cycles are loops all graphs contain cycles, but $G_3$ has two cycles: $\{(a,b), (b,c)\}$ and…
lucidgold
  • 1,054
23
votes
3 answers

Product of adjacency matrices

I was wondering if there was any meaningful interpertation of the product of two $n\times n$ adjacency matrices of two distinct graphs.
RougeSegwayUser
  • 2,871
22
votes
3 answers

What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

Havel-Hakimi Theorem: A sequence s: $d_1, d_2, \ldots, d_n$ of non-negative integers with $\Delta = d_1 \geq d_2 \geq \ldots \geq d_n$ and $\Delta \geq 1$, is graphical if and only if the sequence $$s_1: d_2 - 1, d_3 - 1,…
roxrook
  • 12,081
22
votes
1 answer

Bombing of Königsberg problem

A well-known problem in graph theory is the Seven Bridges of Königsberg. In Leonhard Euler's day, Königsberg had seven bridges which connected two islands in the Pregel River with the mainland, laid out like this: And Euler proved that it was…
Dan
  • 14,978
22
votes
4 answers

How many Hamiltonian cycles are there in a complete graph $K_n$ ($n\geq 3$) Why?

It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation. My textbook, however, says that the answer is $(1/2)(n-1)!$ Unfortunately, it…
mimicocotopus
  • 499
1
2 3
…
99 100