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

2
votes
1answer
100 views

Meaning of Nc in Paul Erdős and Rényi's paper On Random Graphs

In Paul Erdős and Rényi's 1959 paper On Random Graphs I, they describe the number of edges in a random graph by the function (1) Nc = [1/2 * nlogn + cn] where n is the number of nodes in the ...
3
votes
1answer
29 views

On one quantity in a finite graph

Let $(G,E)$ be a finite undirected graph, and $d$ be the usual shortest path distance on $G$. The graph is not necessary connected, so $d(v',v'') = \infty$ if there are no paths from $v$ to $v'$. For ...
4
votes
1answer
105 views

Bound with biclique covering

This concerns a problem from Extremal Combinatorics by Jukna that I cannot solve myself. First some preliminaries. A biclique covering of a graph is a covering of a graph with complete bipartite ...
2
votes
0answers
101 views

Cover times and hitting times of random walks, once again.

This is a followup to my question Cover times and hitting times of random walks. Consider a random walk on an undirected graph with $n$ vertices which, at each step, moves to a uniformly random ...
2
votes
2answers
122 views

Cover times and hitting times of random walks

Consider a random walk on an undirected graph which, at each step, moves to a uniformly random neighbor. Define $T(u,v)$ to be the expected time until such a walk, starting from $u$, arrives at $v$, ...
0
votes
1answer
106 views

Graph in relation to its independence number.

I am working on the statement " A graph $G$ is a $nKn$ (collection of $n$ number of complete graph each of order $n$) graph if and only if $\bar{G}$ is $α(G) = α(\bar{G}) = n$ and $(p-n)$-regular , ...
7
votes
2answers
2k views

How to construct a k-regular graph?

I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical ...
1
vote
2answers
770 views

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only ...
1
vote
0answers
130 views

Randomly Generating Connected Directed Acyclic Graphs

I'm looking for a way to generate random connected directed acyclic graphs, where I can specify the number of vertices that have no outgoing edges (leaf vertices). Anyone ever seen such a thing, or ...
2
votes
2answers
102 views

A trivial planar triangulation with a non-Hamiltonian dual

I'm looking for a simple (or better yet, minimal) example of a planar triangulation of which dual graph (that of the faces) would be "obviously" non-Hamiltonian. (NB: I once asked the same question ...
5
votes
1answer
250 views

Disjoint paths on grid graphs

Let $f(G)$ be the smallest $m$, such that one can find $2m$ vertices in $G$ with the following property: pair up the vertices in any way, and find $m$ paths that join each pair. Then every set of path ...
4
votes
0answers
622 views

Random graph connectivity, and the existence of isolated vertices

Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim: ...
3
votes
1answer
304 views

Sliding blocks puzzle

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square, 1 green, some red and the rest are blue, a move consists of shuffling ...
4
votes
2answers
204 views

Show the graph is regular

If $G$ is a connected finite graph which has no triangles, and $G$ has the property that if two vertices have a common neighbour then they have exactly two common neighbours, does $G$ have to be ...
3
votes
2answers
140 views

Eulerian Graph Question

I'm struggling with the following question: Prove that every Eulerian graph of odd order has three vertices of the same degree. I'm not sure how to proceed with this. If someone could give me a ...
2
votes
1answer
314 views

Give a connected graph whose automorphism group has size 3

Find a connected graph whose automorphism group has size 3. Note: I know such graph must be non-simple.
6
votes
2answers
479 views

What is an inductive graph?

My google search turned up much information about what people are doing with inductive graphs, but no definitions. So I ask you, StackExchange, what is an inductive graph? When I think of induction, I ...
2
votes
1answer
1k views

proof about clique number, adjacency number, and chromatic number

Let G be a graph with n vertices. Prove that the chromatic number of G is greater than or equal to its clique number. Also prove that the chromatic number is greater than or equal to (n/the adjacency ...
0
votes
1answer
123 views

How to apply the Poincaré formula to a regular n-gon?

I've been trying to solve the following home task: Choose $n$ points ($n\ge 2$) on the circle's circumference and connect them all with each other using chords. In result, the circle is ...
2
votes
1answer
1k views

finding a formula for the number of connected components in a graph

Let $n$ and $k$ be integers with $1\le k < n$. Form a graph $G$ whose vertices are the integers $0,1,2,...,n-1$. We have an edge joining the vertices $a$ and $b$ provided $$a-b \equiv \pm k \pmod ...
1
vote
1answer
138 views

A problem about Euler's Formula

I have this problem in my homework but it doesn't seem quite right to me: Every face of a convex polyhedron has at least $5$ vertices, and every vertex has degree $3$. Prove that if the number of ...
1
vote
1answer
77 views

Consequences of Hamilton Paths and Cycles

I'm having a bit of trouble with this homework problem: If $G=(V, E)$ is a connected bipartite undirected graph with $V$ partitioned as $V_1\cup V_2$, how can I prove the existence of a Hamilton path ...
0
votes
1answer
297 views

Graph Theory - Spanning Trees

Consider a graph $G$ composed of two cycles which share an edge. $C_x$ is the cycle of length $x$ and $C_y$ is the cycle length $y$, for $x,y \ge 3$. (for example, if $x = 6$ and $y = 5$, then $C_x$ ...
1
vote
2answers
397 views

Graph drawer in the spirit of Graph Thing

I am looking for a software that can plot graphs in the spirit of Graph Thing. I have been using a little bit this software and I enjoyed the few possibilities that are offered. Some good points: ...
2
votes
1answer
135 views

Graph theory - A type of undirected simple finite graphs

When studying Organic Chemistry, I just came up with a problem, which is following: Problem 1: Let $T$ be the set of undirected simple finite graphs $G(V,E)$ satisfying that $\forall v \in V,$ ...
1
vote
1answer
165 views

Existence of a spanning tree with certain properties

Let $\Gamma$ be a finite, connected graph (multiple edges between two vertices are allowed). Fix a vertex $u_0\in V\Gamma$. Does there exist a maximal subtree (i.e., a spanning tree) $T\subset\Gamma$ ...
6
votes
1answer
148 views

Application of the First Moment Method to Random Graphs

I've been trying for a few days to figure out a proof of part $(iii)$ of Lemma 2.1 of this paper, on page 4, and I could definitely use some help. You don't need to understand any of the rest of the ...
3
votes
2answers
451 views

Show triangulations can be transformed into each other by edge flip.

Let $\Delta_1$ and $\Delta_2$ be two triangulations of the same point set $P_n$. Show that they can be transformed into each other by edge flips. To define an edge flip, let $pqrs$ be vertices (in ...
4
votes
3answers
136 views

Visualizing identity $m\le3n-6$ for simple connected finite planar graphs

How can I visualize the identity $m\leq3n-6$ (where $m$ is the number of edges, $n$ the number of vertices) for simple connected finite planar graphs?
3
votes
0answers
124 views

When is every spanning tree of a connected graph the union of spanning trees of its subgraphs?

Let $G$ be a finite connected simple graph. By the union $H\cup K$ of two graph $H$ and $K$ we shall mean the graph with edge-set $E(H)\cup E(K)$ and vertex-set $V(H)\cup V(K)$. For which ...
1
vote
2answers
164 views

Ramsey theory - colouring of edges

I'm trying to understand a proof: $R(3,3) = 6$ proof: Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is ...
4
votes
1answer
653 views

Probability of cycle in random graph

I create a random directed graph, with N vertices and N edges, in the following process: A. Each vertex has a single outgoing edge. B. The target of that edge is selected at random from all N ...
1
vote
0answers
429 views

the number of shortest path between two points

I know that visibility graph is used to determine the shortest path between two points a mong a set of obstacles in the plane. So in the case that obstacles are triangles, is the maximal number of ...
2
votes
2answers
778 views

Finding all graphs with a certain vertex degree sequence

I've been given the following problem as homework: Q: How many graphs are there (up to isomorphism) with score (3, 3, 3, 3, 3, 3, 6)? Also, do this for (3, 3, 3, 3, 3, 3). The "score" is ...
0
votes
2answers
80 views

What is the most basic graph, and how would you use it in an induction-proof?

Can a single point be a graph? Or is it just a single edge and two vertices? How do you apply this to an induction-proof in graph-theory? thanks
1
vote
1answer
427 views

Proving properties of a simple undirected graph

Given a connected simple undirected Graph (V,E), in which deg(v) is even for all v in V, I am to prove that for all e in E (V,E\{e}) is a connected graph. ...
3
votes
3answers
3k views

How to show that every connected graph has a spanning tree, working from the graph “down”

I am confused about how to approach this. It says: Show that every connected graph has a spanning tree. It's possible to find a proof that starts with the graph and works "down" towards the ...
0
votes
1answer
238 views

Maximum weighted matching on a tripartite 3-uniform hypergraph

There are polynomial algorithms for finding a maximum weighted matching on a bipartite graph, e.g. the hungarian algorithm. Is there such an algorithm for a tripartite 3-uniform hypergraph? What about ...
4
votes
2answers
117 views

Choosing cyclic subgraphs isomorphic to complete graphs

I've been given the following problem as homework: Q: Compute the number of subgraphs of $K_{15}$ isomorphic to $C_{15}$. $K_{15}$ means complete graph with 15 vertices. $C_{15}$ means ...
2
votes
1answer
107 views

How many ways can $N$ edges be added to a labeled cycle graph with $2N$ vertices to produce a simple cubic graph?

Equivalently, how many functions on the set $\{0, 1, 2, ..., 2N-1\}$ satisfy the following conditions? For all $n$, $f(n) \neq n$. For all $n$, $f(n) \neq n+1 ~(\text{mod } 2N)$. For all $n$, ...
2
votes
1answer
139 views

Counting certain paths in a complete graph

Let $K_n$ be the complete graph with $n$ vertices, where the vertices are labelled $1,2,3,\dots,n$. How many paths are there between $v_1$ and $v_n$ that the labels on the path are strictly ...
3
votes
3answers
124 views

Clarification about a statement in Graph Theory

What does this statement mean: "Unlike Eulerian circuits, there is no known necessary and sufficient condition for a graph to be Hamiltonian." I'm confused about the "no known necessary and ...
3
votes
1answer
116 views

Behaviour of the Cayley graph of a group when changing the generating set / Number of ends of a group

Introduction of terminology: Let $G$ be an infinite group and let $S$ be a finite generating subset of $G$ that is symmetric, i.e. $x\in S$ implies $x^{-1}\in S$. Then the relation $g\sim ...
2
votes
1answer
154 views

Longest cycle containing two nodes

We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
8
votes
3answers
323 views

“Phase change” of a purely mathematical system

Every so often I hear people talking about "phase transitions" in purely mathematical or computer-science contexts, where there is no physics in sight. Today, for example, I heard some people talking ...
1
vote
2answers
68 views

Set Partitions and Graph Matchings

Is there a standard text on the theory of set partitions and/or graph matchings? (I ask both in the same question since it seems feasible that there might be texts containing information on both.) I ...
1
vote
2answers
254 views

Complete Bipartite Graph

I am trying to do this problem, but I don't see how it could be true. I think I have a counter example, but I am looking for confirmation. $P_n$ is the graph which is a path of length n. $C_n$ is the ...
2
votes
0answers
45 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
0
votes
1answer
118 views

Construct a graph G for which the is-adjacent-to relation is antisymmetric.

Background: In this a graph is G=(V,E) where V is the set of all vertices and E is a set of 2-element subsets of V. For example: G=({1,2,3,4},{{1,2},{1,3},{2,4}}). E stands for edges similar to a line ...
2
votes
1answer
275 views

Proof involving a minimum weight spanning tree.

Please help with the following homework problem: Let G be an undirected graph, $v: E\to R$ and $w: E\to R$ be two weight functions on the edges of $G$. Let $z: E\to R$ be defined as the sum of ...