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.

learn more… | top users | synonyms

9
votes
2answers
580 views

Two Steps away from the Hamilton Cycle

Assume an at least $2$-vertex connected, cubic, bipartite, planar graph $G$ that contains a Hamilton cycle (HC) $abcdefg\dots yx\dots za$ (in fact $G$ would then have at least four HCs, see here; it ...
2
votes
2answers
667 views

Time series and social network analysis

I am interested about plotting graphs of a phenomenon and study it using tools from social network analysis. Suppose the nodes are time series, and that the links between the nodes are the correlation ...
0
votes
1answer
2k views

Chromatic Polynomials for Graphs

The chromatic polynomial of a graph $G$ is the polynomial $C_G(k)$ computed recursively using the theorem of Birkhoff and Lewis. The theorem of Birkhoff and Lewis states: $c_G(k) = c_{G-e}(k) - ...
1
vote
1answer
204 views

Expected value and probability

A random graph consisting of n vertices and k undirected edges is constructed by repeating the following step k times: Randomly choose 2 vertices without replacement from n vertices, and connect them ...
2
votes
2answers
74 views

show that careful 5COLOR is in NP

We know that 5COLOR problem is NP-complete. careful 5COLOR problem is that: Given a graph G, can we color each vertex with an integer from the set {0,1,2,3,4}, so that for each edge, the colors of ...
1
vote
1answer
116 views

Expressing a relationship in a graph using quantified logic

Express the following using quantified formulae for a simple undirected graph $G = (V,E)$. The predicate P({u,v}) is true when $\{u,e\}\in E$ and false otherwise. The diameter of $G$ is at most 2. ...
2
votes
1answer
94 views

SDR for an infinite set of sets

Let $F$ be a set of nonempty sets. A set $R\subseteq\cup F$ is said to be a system of distinct representatives (SDR) of for every $B\in F$ there exists unique $x\in R$ such that $x\in B$ and $\forall ...
1
vote
1answer
215 views

If $G$ is semi-Hamiltonian, then removing any $k$ vertices results in a graph with at most $k+1$ connected components.

For all graphs $G$, if $G$ is semi-Hamiltonian (contains a Hamilton path, i.e., a path that visits every vertex in $G$), then removing any $k$ vertices results in a graph with at most $k+1$ ...
1
vote
1answer
160 views

General questions on Cayley graphs

In Graph Theory mainly in Cayley graphs there are four general questions " according to Audery Terras" : 'Suppose A is the adjacency operator of a connected regular (undirected) graph $X$ of degree ...
3
votes
1answer
342 views

Showing that the infinite grid is Eulerian

In a post to usenet in 2004, I wrote: I'm currently remembering learning [sic] some (long forgotten) things about Graph Theory via Robin J. Wilson's "Introduction to Graph Theory", 2nd. ed., ...
2
votes
1answer
85 views

How many citations to read before convergence?

So I have the following question assuming I start with N academic papers, though I was thinking to make this simple I start with one academic paper. And say it has C citations, and each one of these C ...
1
vote
2answers
697 views

Graph Theory - Hard Question -Finding for what values of n ≥ 2 is it possible to form a domino ring that uses all of the C(n,2) dominoes

A domino is a $2\times1$ rectangle. On each half of the domino is a number denoted by dots. In the figure, we show the ten dominoes whose pairs of numbers correspond to pairs chosen from ...
20
votes
1answer
1k views

The $n$ Immortals problem.

I saw this riddle posted on reddit a long time ago, called the "Seven Immortals." In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and ...
3
votes
1answer
96 views

Cheeger's inequality: Markov chain version is a special case of graph version?

For a Markov chain the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a ...
3
votes
1answer
60 views

“We cannot create new cycles by deleting a vertex”

"We cannot create new cycles by deleting a vertex" - How is this true within this context?: "Assume G is planar and has girth at least 6. If v is a vertex of degree at most 2, then G-v still has ...
3
votes
0answers
29 views

How do you find a subset D of set A such that |D| > |N(D)| in a bipartite graph with bipartition A, B (or prove that no such set exist)?

I know that the Hall's Theorem states that there is a matching saturating every vertex in A if and only if every subset D of A satisfies $|N(D)| \ge |D|$, and if I take the contrapositive of the "if" ...
-1
votes
1answer
110 views

Graph Theory - Finding Relation

Let $G = (V,E)$ be a simple and an undirected graph. Define a relation $R$ on the vertices of $G$ as follows: for two nodes $u$ and $v$, $(u,v) \in R$ if and only if there is a path from $u$ to $v$ in ...
0
votes
1answer
197 views

Graph Theory - Euler circuit , trail

Consider a complete tripartite graph $K_{\ell,m,n}$ a. Please draw $K_{2,2,3}$. b. For general values of $\ell,m$, and $n$, how many vertices are in $K_{\ell,m,n}$? c. How many edges are ...
1
vote
2answers
482 views

Graph Theory - Finding Number of paths

Consider a directed graph $D(n)$ whose vertex set $V$ consists of the integers $1,2,\dots,n$, and whose edge set $E$ consists of ordered pairs of integers $(i,j)$ whenever $i < j$. In other ...
1
vote
0answers
66 views

edge appearance probability and conditional independence

So I'm doing research on graphical models and on page 362 of http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf, it says that "if $\beta_{uv}=0$ (i.e. weight of edge $uv$ is zero), edge $e_{uv}$ ...
1
vote
2answers
394 views

Graph Theory mixed with probability - hard question

Suppose we wish to construct a graph in the following manner: Denote the vertices of the graph as $1,2,\dots,n$. For every pair $\{i,j\}$, we flip a fair coin. If it comes up tails, $\{i,j\}$ is an ...
1
vote
1answer
86 views

Proof related to breadth first search

Suppose a connected graph G has a cycle C of length n. Prove that in any breadth-first search tree of G, any two vertices in C are at most $\lfloor\frac{n}{2}\rfloor$ levels apart. No idea how to ...
0
votes
2answers
910 views

How to determine whether the pair of graphs is Graphs Isomorphic

If two graphs $G_i$ and $G_j$ are isomorphic, please provide a bijection from the vertex set of $G_i$ to $G_j$, if the two graphs are not isomorphic, please provide a structural difference graphs ...
6
votes
1answer
373 views

What is graph theory interpretation of this linear programming problem?

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy $$\alpha(G \boxtimes H) = ...
0
votes
1answer
302 views

Hamiltonian & Eulerian paths, one vertex graph

Does the graph with only one vertex have an Eulerian path? And, does it have a Hamiltonian path?
1
vote
2answers
357 views

Breadth first search tree's cycles [duplicate]

Possible Duplicate: Proof related to breadth first search I'm trying to prove the following: Suppose a connected graph $G$ has a cycle $C$ of length $n$. Prove that in any breadth-first ...
1
vote
1answer
324 views

Hint on proving this inequality for a planar graph?

Let $G$ be a connected planar graph with $p$ vertices, where $p \geq 3$. Let $t$ denote the number of vertices in $G$ with degree less than $6$. Prove that if $G$ has no cycles then $t \geq ...
4
votes
1answer
75 views

A group and an associated digraph

I am trying to understand the proof of the following statement: Let $\Gamma=\{g_1,\cdots,g_n\}$ be a group. Define a digraph $G$ by joining $g_i$ to $g_j$ by an edge of color $k$ if ...
2
votes
3answers
441 views

Multipartite graphs which are not planar

Please take a look at these definitions: A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where $n > 1$, $r_1, \ldots, r_n\ge 1$, such that The set of nodes of the ...
0
votes
1answer
58 views

Related to Hall's Theorem

I do not understand the emphasized inequality: http://s11.postimage.org/gnnf1yirn/Capture.png How is it that if the size of X is greater than n, then the number of its neighbours is greater or equal ...
5
votes
2answers
357 views

Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?

My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
2
votes
1answer
467 views

The number of connected components of a $k$-regular graph equals the multiplicity of k

In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components. The ...
1
vote
0answers
42 views

Normalized Cuts and Spectra

I'm looking for a fleshed out proof of the following theorem. Theorem: Let $G=(V,\mathbf{W})$ be an undirected, edge-weighted graph with normalized Laplacian $\mathbf{L}_N$. Furthermore, let ...
3
votes
1answer
307 views

probabilities in Random Graphs

I am trying to find the probability of a bernoulli random graph on $n=10$ vertices with probability that an edge connects any pair of vertices is $p=\frac{1}{6}$ as $n\to \infty$. This is what I ...
6
votes
2answers
533 views

Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges ...
3
votes
1answer
134 views

Number of squares in a hypercube

I am trying to count the number of $4$-cycles in the hypercube $Q_n$. Clearly if $x,y$ are two distinct vertices with two common neighbors then we get a $4$-cycle. But how do I count such $x$ and $y$? ...
0
votes
1answer
142 views

Planar graph with all drawing topologically isomorphic , but whose planar embending are not equivalent

I have to find an exemple on a 2-connected planar graph whose drawing are all topologically isomorphic but its planar embeddings are not equivalent. I thought to use an cycle and some overturning to ...
1
vote
0answers
29 views

Plane graph combinatorially isomorphic to one with all edges straight

I have this problem. I have to show that every plane graph is combinatorially isomorphic to a plane graph whose edges are all straight. I Also have an hint that says to give a plane triangulation and ...
0
votes
1answer
361 views

Adjacency matrices needed for common graphs

I'm making a program which requires adjacency matrices of undirected graphs. In particular, I'd like the adjacency matrices for the graphs in this wiki link: ...
-1
votes
1answer
563 views

Hamiltonian Cycles and minimum vertex degrees

Take a graph $G$ on $n\ge 4$ vertices and suppose that every vertex has degree at least $\frac12n$. Does $G$ necessarily contain a Hamiltonian cycle? (Either give a proof or provide a ...
0
votes
1answer
553 views

How to find the maximum number of vertices in a tree with respect to maximum path length and maximum degree value

Given a tree, find the maximum number of vertices $v$ in that tree using the maximum path length $p$ and a maximum degree that applies to all vertices $d$. Assuming that I drew my test tree ...
3
votes
0answers
119 views

Quantities measuring the sparseness of a graph and of a matrix?

What are some quantities often used to measure the sparseness of a graph? For example, in a graph, with the number of vertices fixed, the smaller the maximum degree is, the more sparse the graph is. ...
2
votes
1answer
124 views

Having a forest and making it into a tree?

Let F be a forest with 100 vertices and 90 edges. How many new edges must be added without adding vertices to obtain a tree? This is what I have so far for this question... I don't think it's this ...
2
votes
2answers
109 views

graph theory /combinatorics committee existence

I'm having trouble figuring out the problem below. I've laid out my approach and it seems combinatorics formulas might help solve this. If anyone can point to me to the right direction i would greatly ...
0
votes
0answers
782 views

Meanings of expansion and expander?

From Wikipedia Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of ...
1
vote
1answer
3k views

Algorithm to check whether a graph has no cycles

Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of ...
0
votes
2answers
433 views

Vertex Cover degree problem

So Vertex cover (VC): Instance: a graph $G$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$? We will now define a version of this problem in which we assume that ...
0
votes
3answers
2k views

Isomorphism between two particular graphs

Are these two graphs isomorphic?
7
votes
2answers
1k views

Even cycles in a graph

I'm at a dead end with the following question, It seems simple enough but I cant seem to see it. Let G be a simple undirected graph with minimal degree 3, show that G contains an even cycle. Thanks. ...
77
votes
1answer
2k views

Number of simple edge-disjoint paths needed to cover a planar graph

Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is ...