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
2answers
26 views

Prove a simple connected graph with n nodes and at least n edges has a cycle.

Proof that a graph with n nodes and m edges such that $ m \geq n \geq 3 $ has a circuit After thinking about it for a while, I have few directions of how to approach the problem, yet I seem to be ...
4
votes
0answers
43 views

Odd Town Problem.

QUESTION: A town with $n$ inhabitants has $m$ clubs such that each club has an odd number of members and any two different clubs have an even number of common members. Show that $m\leq n$. ...
2
votes
1answer
53 views

Removing two adjacent edges so that the graph remains connected

Assertion: From any connected undirected graph it is possible to remove1 two adjacent edges such that the graph remains connected. It is obvious that one can always remove1 one (and by induction, ...
1
vote
1answer
40 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
0
votes
1answer
24 views

Graph Theory Question Related to Domination number.

Let G be a graph whose diameter is at least 3. Prove that the domination number of the complement of G is at most 2. I know that since the diameter of G is at least 3, the diameter of the complement ...
0
votes
0answers
13 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
7
votes
1answer
66 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
5
votes
1answer
37 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
0
votes
0answers
8 views

How do I show that the Turàn density exists?

I have the extremal/Turàn function defined as $$ \operatorname{ex}(n, F) = \max\left\{e(G): |G| = n, F \not\subseteq G\right\} $$ and the Turàn density $$ \lim_{n \to \infty} ...
1
vote
1answer
28 views

Order of cycles in graph

In a school assignment, I am to use contradiction to prove that if a graph is bipartite then all of its cycles have even order. In this context, what does it mean for a cycle to have even order? I ...
2
votes
1answer
54 views

Easy to read books on Graph Theory

I was asked to read about Graph Theory. First got the book "Graph Theory with Applications" by Bondy and Murty. As a Computer Science student its becoming difficult to read and understand. Then I ...
0
votes
1answer
15 views

What is meant by “restriction” in subgraph defintion

In the book "Graph Theory with Application" by Bondy and Murthy it is defined that A graph $H$ is a subgraph of G if $V(H) \subset V(G)$, $E(H) \subset E(G)$ and $\psi_H$ is the restriction of ...
0
votes
1answer
17 views

Max flow min cut algorithm

I am trying to work this max-flow, min-cut out for my finals, but Im really not sure I have got it, I would appreciate some assistance! I understand the theorm, I comes from ford-fulkerson, where the ...
1
vote
1answer
23 views

Existence of a (19, 6, 1, 2) strongly regular graph

While reading Is there a graph with 99 vertices... I became curious about smaller graphs satisfying the property. According to Wikipedia, strongly regular graphs must satisfy the relation: ...
2
votes
1answer
22 views

Given an undirected connected graph, how many orientations would maintain acyclicity

Given an undirected connected simple graph $G=(V,E)$ there are $2^{|E|}$ orientations. How many of these orientations are acyclic?
0
votes
0answers
11 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...
0
votes
0answers
27 views

Erdos-Renyi Model Intuition

I was reading the Wikipedia article on the Erdos-Renyi model and I was wondering how they came up with the probability for each connection. I see that there are $n \choose 2 $ nodes to check out, but ...
0
votes
1answer
46 views

How many non-isomorphic, connected graphs are there on $n$ vertices with $k$ edges?

I'm a non-mathematician working with applied graph theoretic tools. I need to figure out how many possible graphs exist for a problem of mine (in a graph structure optimization problem, quickly said). ...
0
votes
0answers
24 views

How to know if Harary graph [n, k] is planar [on hold]

How do I figure if a Harary graph [n, k] is planar?
0
votes
2answers
40 views

Expected Value with graph theory

A group of $n\geq 3$ people is sitting at a round table, so that each person has two neighbors,one clockwise neighbour and one counter clockwise neighbour. Each person flips a fair and independent ...
0
votes
1answer
25 views

What's maximal clique?

I'm unable to understand what maximal clique is. I mean how a clique can't be extended by a node and remain a clique? If I add a node and then I connect this node to every other nodes in the clique, ...
2
votes
1answer
51 views

Confusion regarding steps in bipartite matching proof

Can someone please explain how it follows that $|N(S)|x \geq |S|x$? What I'm asking is why is it necessary to use the value of x to derive the inequality? Theorem 5.2.7. Let G be a bipartite graph ...
1
vote
1answer
51 views

Ore's Theorem Question

I was reading the proof of this Theorem in the Book "Graphs and Digraphs" of Chartrand (Link to the proof (Page 94-95)) and there's something that I don't understand. This part says: Hence for ...
0
votes
1answer
62 views

A question about rational number.

Denote $M$ as a $m\times n$ matrix whose components are all nonnegative integers (actually 0 or 1) and $1$ as the $m$ dimensional vector $(1,1,\cdots,1)$. Show that: There is a vector $x_0$ ...
0
votes
1answer
34 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
0answers
20 views

mean number of links in adjacency matrix

I have converted from an individual-level adjacency matrix to one for clusters and I am trying to show mathematically how I programmed up determining the mean number of inter-cluster links. I am not ...
0
votes
1answer
26 views

Chromatic Equivalence Requirements

I have searched and searched and am unable to find the answer that I am looking for. I am trying to determine the conditions required for two graphs to have the same chromatic polynomial. On both ...
2
votes
0answers
42 views

Maximum number of edges in a (n,n) bipartite graph, that doens't have a complete bipartite subgraph $K_{r,r}$

I need to prove that the maximum number of edges in a $n \times n$ bipartite graph, that doens't have a complete bipartite subgraph $K_{r,r}$ is lower bounded by $cn^{2-2/(r+1)}$ where c is a constant ...
2
votes
1answer
34 views

Quasi-isometry of Schreier coset graphs

Let $G$ be a finitely generated group and $H$ a subgroup. For any choice of a generating set $X$ we can form the Schreier coset graph. Is this graph independent of the generating set up to ...
1
vote
1answer
21 views

Power series convergence of random walk transition matrix

I would like to find out if $$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$ where $P = D^{-1}W ~ $ is a random walk transition matrix. $W$ is a matrix describing weights in a graph and ...
1
vote
2answers
40 views

What is the difference between a simple graph and a complete graph?

I might be having a brain fart here but from these two definitions, I actually can't tell the difference between a complete graph and a simple graph.
2
votes
2answers
34 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
-1
votes
0answers
27 views

vertex magic total labelings [on hold]

Lemma If $G$ has a vertex-magic total labeling, then the number of edges $e$ and the number of vertices $v$ satisfy $e\ge\dfrac{2v}{3}$. How to prove this lemma? Here's the original statement:
1
vote
1answer
37 views

Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it. Prove that if graph $G$ is a 3-connected planar graph then its ...
1
vote
2answers
56 views

Combinatoric Graph [on hold]

Draw a graph whose nodes are the subsets of {a,b,c} and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element? I'm having a really hard time understanding ...
1
vote
1answer
69 views

Bipartite Graph

Is there a bipartite graph with the following degrees: 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6, 6? I've tried so many different combinations and I don't think there is a way to make a bipartite graph this ...
0
votes
1answer
79 views

When graph theory cannot model the most basic problem in wireless networks. Why?

I have a set of wireless links. These links are denoted by $\mathcal{L}=\{\ell_1, \dotsc, \ell_n\}$. Every link $\ell_i$ is composed of one transmitter $s_i$ and one receiver $r_i$. Initially, all ...
0
votes
2answers
38 views

Finite trees and embedding in infinite regular trees.

Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also ...
4
votes
1answer
60 views

What's the number of possible structures of alkanes $C_n H_{2n+2}$?

When my chemistry teacher started listing out all possible structure of the hydrocarbon $C_7H_{16}$, my mind flied to look for a general formula. Let me mathematicalize this problem. Here, we have ...
0
votes
0answers
35 views

Graph planarity, Demoucron's algorithm

I need to implement Demoucron's algorithm for planarity testing and embedding. Testing is relatively easy to implement but embedding is the main problem. At some point, I need to draw some path ...
1
vote
1answer
40 views

Hamiltonian Paths in Complete Graphs

A bit of background to help explain the question: In a class we were given a large spreadsheet of stars and were asked to find two paths, starting from the Sun and visiting every star within 10 ...
-2
votes
2answers
28 views

Question over $0$-regular graphs [closed]

Show that if G is a $0$-regular graph then $k(G)= \lambda (G)$ I know this to be true, but how do I show it?
0
votes
0answers
33 views

Independent set of edges contained in a maximum independent set of edges

Every independent set of edges in a graph is contained in a maximum independent set of edges I know this statement is true but how do I prove it?
0
votes
1answer
17 views

Proving minimum vertex cover

Every vertex cover of a graph contains a minimum vertex cover. I know the statement to be true but how do I go proving it?
1
vote
1answer
44 views

Is a butterfly network on 8-inputs planar?

I could prove that a four input butterfly network is planar. For that I simply drew it such that no two edges intersect. But I could not use the same approach for the 8-input butterfly network. So I ...
1
vote
1answer
23 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
2
votes
0answers
39 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
0
votes
0answers
64 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
0
votes
2answers
46 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
0
votes
1answer
20 views

uniqueness of Maximal Independent Set(MIS)

Is maximal independent set of a graph unique? I think between indepent sets, only one of them is maximal. So does it prove that MIS is unique?