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

7
votes
4answers
136 views

Graph on the cover of Bollobás's “Combinatorics”

I was browsing the library and I found Bela Bollobás book "Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics" and, on its cover, it has a graph that I don't ...
2
votes
2answers
21 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
vote
2answers
19 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.
-1
votes
0answers
13 views

vertex magic total labelings [on hold]

If G has a vertex-magic total labeling, then number of edges is more than equal to 2 time number of vertex/3
0
votes
0answers
5 views

Number of self-links, feedforward, feedback loops

Suppose we have a graph with N* nodes (N* is the number of internal nodes). Every directed link in the network exists with probability p. What would be the expected number of: self-links ...
1
vote
1answer
25 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
41 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 ...
0
votes
3answers
26 views

Proving the distance between 2 vertices

Let $G$ be a disconnected graph. Then, I know $\bar G$ is connected. Prove that if $u$ and $v$ are any two vertices of $\bar G$, then $d_{\bar G}(u,v)=1$ or $d_{\bar G}(u,v)=2$ Then I also know if ...
0
votes
2answers
43 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 ...
1
vote
1answer
56 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
63 views

How to determine number of isomorphic classes of simple graph with n vertices, each with degree m?

For HW, I need to find the number of isomorphic classes of a simple graph with 7 vertices, each with degree two. I know I could brute-force it by finding all edge sets that fulfill that criteria, but ...
0
votes
1answer
75 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 ...
2
votes
2answers
113 views

Question about edge coloring and perfect matchings in regular graphs

On the wiki page for edge coloring says the following two things: "If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges ...
1
vote
1answer
37 views

Random Graphs: Examples of their Uses

Just writing a paper at the moment on random / random geometric graphs. If any of you could perhaps give examples, as broad and interesting as possible, of where these have been used across science? ...
0
votes
1answer
29 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
4
votes
1answer
57 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 ...
11
votes
1answer
599 views
+100

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go . . . ] Here's my description of the game: There's a $4\times 4$ grid with some random, numbered cards on. The numbers are either one, two, or multiples of three. ...
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
0answers
44 views
+50

Does any vertex transitive graph have a bounded eigenvector?

Following up on the negative answer to this question, I would be interested in knowing the answer to the following question, which I cannot seem to find an obvious contradiction to when testing for ...
0
votes
2answers
50 views

what is the maximum number of non loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
1
vote
1answer
35 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 ...
1
vote
2answers
28 views

Edge-Connectivity of a graph

If $G$ is a graph of order $n$ such that $\delta(G) \geq (n-1)/2$, then $\lambda(G)= \delta(G)$ So I know this statement to be true. How would I prove this statement?
-3
votes
2answers
25 views

Question over $0$-regular graphs [on hold]

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
32 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
12 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
43 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 ...
8
votes
1answer
209 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
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?
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) ...
0
votes
1answer
23 views

edge chromatic number of regular graphs [on hold]

prove that a graph G that is k-regular and exactly n vertices which n is odd ,has the index chromatic number of maximum degree.
2
votes
0answers
37 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
54 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 ...
1
vote
2answers
25 views

Graph theory maximum cardinality?

describe an algorithm that finds as efficiently as possible a matching of maximum cardinality in any bipartiate graph I know that matching means that in the graph no two edges share a common vertex. ...
0
votes
1answer
23 views

How many isomorphisms do these iso classes of 5 edges and 5 vertices have

Hello, I am referring to the second and third graphs. The second graph should have 60 isomorphisms but I can't see how. I thought it should be (5 choose 1) for a and then (4 choose 2) for the ...
0
votes
1answer
59 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
3
votes
1answer
251 views

Lower bound of the probability of minimum degree?

Suppose you have a graph, say a geometric random graph, with $n$ nodes where each link appears with probability $p$. Assuming $E_k$ is the event that the graph has minimum degree $k$, is it possible ...
0
votes
2answers
19 views

Inequality regarding diameter, maximum order and number of vertices.

Suppose I have a connected graph on $n$ vertices with maximum degree $x$. What is the minimum value of the Diameter $D$?
-1
votes
1answer
27 views
1
vote
1answer
23 views

How many automorphisms does the second graph have

Hello, the second graph should have 2 automorphisms, but I see that none of the vertices has exactly the same adjacent vertices, so that I would be able to switch them and form an automorphism. What ...
0
votes
1answer
12 views

Discrete math on multipartite graph

I am wonder about these problem 1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ 2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$
0
votes
0answers
25 views

Some problems on Graph [on hold]

I have some difficult problems. I would like you to give some ideas. Thank you in advance. Let $G = (V;E)$ be a connected graph with $n$ vertices and $m$ edges. Consider the set $W$ of all spanning ...
0
votes
1answer
27 views

How many isomorphic graphs does this iso class of 5 vertices and 5 edges have?

I am referring to the second graph. It has 60 graphs, but I can't seem to understand why. What i have so far is that there are (5 choose 2) ways of picking b and d combo; but what do I times this by ...
-1
votes
0answers
20 views

how many simple graphs of 5 vertices and 5 edges [duplicate]

This class has 4 automorphisms and 30 isomorphisms, so the total number of graphs is 120. But the formula I have for simple graphs says that the total number of graphs is (possible edges choose ...
0
votes
1answer
24 views

Please explain why this isomorphic class has 30 graphs and 4 automorphisms

Please explain why this iso class with 5 vertices and edges has 30 graphs and 4 automorphisms. I understand there are 5 ways to choose a, but then where does 4 choose 2 come in? Please help. This is ...
2
votes
1answer
26 views

Forbidden toroidal minors

A finite graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. Is there a (finite) set of minors that can classify if a graph is toroidal?
0
votes
2answers
33 views

Given a directed graph, count the total number of paths of ANY length

Given a directed graph, how to count the total number of paths of ANY possible length in it? I was able to compute the answer using the adjacency matrix $A$, in which the number of paths of the ...
0
votes
0answers
56 views

Matrix graph and irreducibility

How do I prove that if $A\in\mathbb C^{n\times n}$ is a matrix then it is irreducible if and only if its associated graph (defined as at Graph of a matrix) is strongly connected?
2
votes
1answer
54 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
3
votes
1answer
279 views

Maximum cycle in a graph with a path of length $k$

I don't understand why this stands: Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Then $G$ contains a cycle ...