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

0
votes
2answers
807 views

no cycles if and only if has $n-m$ connected components

Let $G=(V,E)$ a graph. Prove that $G$ has no cycles if and only if $G$ has $n-m$ connected components where $n$ is the number of vertices of $G$ and $m$ is the number of edges of $G$. The thing I did ...
1
vote
0answers
51 views

Complexity of integer assignment to hypercube vertices?

I came across this problem whilst studying Gray codes during some current optimisation work. It seems likely to me that the complexity of it may be known. However, my background is not in computer ...
0
votes
1answer
49 views

Proofs by saturating graphs

Recently I saw some graph theory proofs works like the following: Theorem: If A then B. Proof: Assume G be a counterexample of A, then saturate the graph(as in add edges) until adding any edge will ...
13
votes
1answer
253 views

Help with a Bollobás proof - Switching between random graph models

I'm trying to make my way through Bollobás' book 'Models of Random Graphs', and unfortunately I've come entirely unstuck on one of his typical 2-line "and of course, this is entirely trivial"-style ...
9
votes
2answers
752 views

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.
2
votes
0answers
65 views

Proof that for any graph, $|E| \leq (|V| - k +1)(|V|-k)/2$

I'm trying to prove that for any simple graph $G=(|E|,|V|, f)$ $|E| \leq (|V| - k + 1)(|V| - k) /2$ Where |E| - number of edges, |V| - number of vertices, and k - number of components. Attempt at ...
2
votes
1answer
900 views

Disjoint edges between vertices of odd degree

This is a problem from Algorithms by Dasgupta, Papadimitriou, and Vazirani (problem 3.27): Two paths in a graph are called edge-disjoint if they have no edges in common. Show that in any ...
2
votes
2answers
2k views

Proof that any simple connected graph has at least 2 non-cut vertices.

I'm trying to prove that any simple connected graph with at least $3$ vertices ($|V| \ge 3$) has at least $2$ vertices whose removal will not lead to the increment of number of components. In other ...
1
vote
1answer
172 views

Graph Path crossing all Edges

I can't come up with an eficcient way to, given a graph, find a path that crosses all edges, only once per each edge, and end in the same vertex that it started. Can anyone point me in the right ...
4
votes
1answer
203 views

minimum number of vertices for a specific graph

Today I saw this problem: Find the smallest $n\ge 5$ such that there exists a simple graph on $n$ vertices such that any two adjacent vertices have no common neighbours, and any two non-adjacent ...
1
vote
1answer
1k views

Eulerian walk proof: If a connected graph has exactly two nodes with odd degree, then it has an Eulerian walk?

Prove that: If a connected graph has exactly two nodes with odd degree, then it has an Eulerian walk. Every Eulerian walk must start at one of these and end at the other one. How shall I prove this?
1
vote
1answer
370 views

Transitive reduction: calculating “relation composition” of matrices?

I have graphs represented by matrices. For example, $\begin{matrix} 0&0&0\\1&0&0\\1&1&0\end{matrix}$ Produces this graph: The graphs are supposed to be transitive, i.e. ...
10
votes
3answers
281 views

Etymology of “topological sorting”

This may be a dumb question, but what's "topological" about topological sorting in graph theory? I thought topology was related to geometry and deformations.
1
vote
0answers
74 views

determine the max flow function $f^*$ in a network given the maximum flow value

Suppose I have a Network N ( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out) ...
7
votes
1answer
599 views

Proving that the complement of a bipartite graph is perfect

In Section 1.6 of Harris et al.'s book Combinatorics and Graph Theory, there is a question asking to show that the chromatic number equals the clique number for the complement of a bipartite graph. I ...
1
vote
1answer
786 views

Connectivity in Graphs: removing edges vs. removing vertices

For a simple undirected connected Graph $G(V,E)$ I say the edge $xy \in E(G)$ disconnects G if the resulting graph G' does not have a path from every vertex to every other vertex. Now suppose I have ...
11
votes
5answers
2k views

Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
9
votes
1answer
5k views

How many non-isomorphic graphs with n vertices and m edges are there?

Could someone tell me how to find the number of all non-isomorphic graphs with $m$ vertices and $n$ edges. (The graph is simple, undirected graph) In my particular problem, $m =20, n=180$ Attempt at ...
1
vote
0answers
126 views

Spielman. Spectral Graph Theory Proposition

Spielman says in Lecture 3: Laplacians and Adjacency Matrices Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
1
vote
0answers
119 views

'Rank' in a hypergraph

I'm teaching myself about hypergraphs and can't get my head around a statement in the book I'm using which seems just plain wrong. Hopefully someone here can explain why either I'm misunderstanding ...
1
vote
1answer
333 views

Bipartite graph non-isomorphic to a subgraph of any k-cube

Find a bipartite graph that is not isomorphic to a subgraph of any k-cube
1
vote
2answers
83 views

Properties of an element $x\in X$ in the Cayley-Graph $\Gamma(G,X)$ of a group G.

My problem ist the following: Let G be a group with generating set X. We can look the Cayley-Graph $\Gamma(G,X)$ of G. Let $x\in G$. Then it holds: $d_{\Gamma}(v,xv)\leq 1$ f.a. $v\in G=\Gamma(G,X)$ ...
1
vote
0answers
209 views

Finding the number of spanning trees of a given height

I hope I can avoid being confusing, but here goes. I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
10
votes
4answers
516 views

Probability of global epidemic

Consider $\mathbb{Z}^2$ as a graph, where each node has four neighbours. 4 signals are emitted from $(0,0)$ in each of four directions (1 per direction) . A node that receives one signal (or more) at ...
1
vote
1answer
179 views

Vertex Cover Problem

How to show that in every graph, the minimum size of a vertex cover is equal to number of vertices minus the maximum size of an independent set. According to Vertex cover two problem are not ...
17
votes
2answers
859 views

Self-avoiding walk on $\mathbb{Z}$

How many sequences $a_1,a_2,a_3,\dotsc$, satisfy: i) $a_1=0$ ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$) iii) $a_i\neq a_j$ for $i\neq j$ iiii) $\mathbb{Z}=\{a_i\}_{i>0}$ Are the two alternating ...
1
vote
1answer
206 views

Is a line considered a face in graph theory?

Is a line considered a face in graph theory? For example just a straight line point to point. 0-------------------------0
1
vote
2answers
268 views

Graph Theory Question Confused

Im confused to this question. Can someone lead me in the proper way? The degree of a vertex is defined as the number of edges touching it. Let’s define in an analogous way the degree of a face to be ...
0
votes
0answers
45 views

probability that adding the ith random edge will increase the size of maximum matching by 1

In a random graph of $i-1$ edges, I need to find the probability that adding the $i$-th random edge will increase the size of maximum matching by 1. Is there any way to calculate this probability or ...
0
votes
0answers
127 views

When is the union of two acyclic subgraphs (of a digraph) still acyclic?

Let $D$ be some directed graph, and let $G$ and $G'$ be two acyclic subgraphs of $D$; let $E$ and $E'$ be their sets of edges. Is it possible to give a simple criterion on $E$ and $E'$ ...
3
votes
0answers
143 views

How to solve equation involving binomial coefficient?

I'm reading this paper which says If we have $$ \binom n d p^{\binom d 2} = 1 $$ where $ 0 < p \le 1$, then $$ d = 2 \log_bn - 2 \log_b \log_b n + 2 \log_b\left(\frac 1 2 e\right) + 1 + O(1) ...
1
vote
1answer
274 views

Simple Example of Dependency Digraph that is Not a Dependency Graph

In the language of the Lovász Local Lemma, a dependency graph $G$ is one in which each $i$ vertex corresponds to an event $A_i$ and each event $A_i$ is mutually independent of the collection $\{A_j ...
11
votes
1answer
323 views

Random graph probability lemma

I'm trying to prove a fiddly lemma for homework, but getting absolutely nowhere with it. Here, $G_{n,p}$ and $G_{n,m}$ represent, respectively, random graphs on $n$ vertices where the number of edges ...
7
votes
1answer
498 views

Showing that $K_7$ contains at least 4 monochromatic triangles

A problem in my book is: Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic ...
1
vote
2answers
164 views

What are the two connected (vertex) transitive graphs with $n=8$, $\deg(G)=3$?

According to McKay in McKay, Brendan; Royle, Gordon F.; The transitive graphs with at most $26$ vertices. Ars Combin. 30 (1990), 161-176., there are exactly 2 isomorphically distinct graphs with 8 ...
2
votes
0answers
53 views

Dehn Twist in the sense of graphs

Does anyone knows a good book or script about Dehn Twists in the sense of graphs. More precisely: I need to know how a Dehn Twist yields an automorphism of a group or subgroups. I want to know ...
3
votes
1answer
331 views

extending bipartite Graphs to regular bipartite Graphs

I am working on this problem trying to show for a bipartite graph $G$ when given $k \in \mathbb{N}$ such that $k$ exceeds the degree of each vertex $v \in V(G)$ I can construct a new graph $G'$ ...
5
votes
1answer
70 views

Interpretation of a simple probabilistic term in a calculation

I'm reading through my notes on the evolution of random graphs and have come unstuck trying to figure out the meaning of a probabilistic term which appears, and was hoping you could help - it's not ...
4
votes
2answers
242 views

Graph-Minor Theorem for Directed Graphs?

Suppose that $\vec{G}$ is a directed graph and that $G$ is the undirected graph obtained from $\vec{G}$ by forgetting the direction on each edge. Define $\vec{H}$ to be a minor of $\vec{G}$ if $H$ is ...
7
votes
1answer
484 views

Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board. At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
1
vote
1answer
190 views

Graph coloring problem: existence of at least three vertices

I am trying to prove the following: Fix an integer $d ≥ 3$. Let $H$ be a simple graph with all degrees $≤ d$ which cannot be $d$-colored and which is minimal (with the fewest vertices) subject to ...
3
votes
2answers
159 views

Inverse limits of graphs

A (directed) graph $\Gamma$ is usually defined as a pair $(V,E)$ where $V$ is the set of vertices and $E \subseteq V \times V$ is the set of edges. A morphism of graphs $\Gamma$ and $\Gamma'$ is ...
1
vote
0answers
38 views

Necessary condition for any two vertices to share at least one common neighbor in a graph [duplicate]

Possible Duplicate: Lower bound on number of edges in “triangular” graph I am looking for a necessary condition, in terms of number of edges, in order to make any two vertices ...
2
votes
0answers
90 views

How matroids can help me locating trees inside a graph?

Background I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids? What I am looking for ...
0
votes
1answer
123 views

Can we find a map for a non-planar graph? how to prove it?

A geographical map can always be modeled as a graph, such as the famous four-color problem. Does a graph always correspond to a map? In my point of view, planar graph can be done. So...  Is there any ...
0
votes
2answers
224 views

Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure ...
0
votes
1answer
77 views

planar embedding a graph

Let $G$ a planar graph and $e$ an edge of $G$. Describe a way (method) to give a planar embedding of the graph such that $e$ is in the outer face of the graph. Any help? Thank you!
1
vote
1answer
152 views

Parity Condition

In the proof for the NP-completeness of Edge-colouring (paper), there is an intermediate result used called the parity condition, which is formulated in a lemma. Quoting from the paper: Let $G$ be ...
6
votes
2answers
367 views

Lower bound on number of edges in “triangular” graph

Question I found in one of the previous year's exam: Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq ...
1
vote
0answers
62 views

Graph classes equivalent to circular-arc graph

I'm looking for properties of circular-arc graphs, mainly its equivalence relations with more common graph classes. Simular to properties such as $\mathit{interval} \equiv \mathit{chordal} \cap ...